Temperature-induced variations of elastic moduli in solid media are generally characterized by a strong nonlinear dependence on temperature associated with complex deformations under thermal treatments. Conventional thermoelasticity with third-order elastic constants for the one-order temperature dependence has been extensively studied for crystals, but encountering problems of divergent and limited velocity variations for rocks as a polycrystal mixture, especially at high temperatures. The extension of the theory beyond high-order elastic constants to solid media is addressed in this article to describe the nonlinear temperature dependence of both elastic constants and wave velocities. The total strain is divided into the background component associated with temperature variations and the infinitesimal component induced by propagating waves. A third-order temperature dependence of velocity variations is formulated by taking into account fourth-order elastic constants. Applications to solid rocks (sandstone, granite, and olivine) demonstrate an accurate description of temperature-induced variations, especially for high temperatures. Unlike crystals, the synthetic averaging elastic constants for a solid rock (as a polycrystal mixture) change less than 10% with temperatures. The thermal sensitivity of P-wave velocities is much more than that of S-wave velocities over the vast majority of temperatures examined.