A first-principles-based computational tool for simulating phonons of magnetic random solid solutions including thermal magnetic fluctuations is developed. The method takes fluctuations of force constants due to magnetic excitations as well as due to chemical disorder into account. The developed approach correctly predicts the experimentally observed unusual phonon hardening of a transverse acoustic mode in Fe-Pd an Fe-Pt Invar alloys with increasing temperature. This peculiar behavior, which cannot be explained within a conventional harmonic picture, turns out to be a consequence of thermal magnetic fluctuations. The proposed methodology can be straightforwardly applied to a wide range of materials to reveal new insights into physical behaviors and to design materials through computation, which were not accessible so far.