A nonlinear dispersion relation is derived for acoustic-gravity waves which includes nonlinear frequency shifts as well as nonlinear damping decrements (attenuations). The nonlinear damping decrement was derived in a previous paper. Here, a calculation is made of the nonlinear frequency shift. This calculation is based on the method of perturbed particle orbits (perturbed orbits). Explicit expressions are derived for the frequencies of gravity waves in terms of the mean square wave amplitude and wave spectrum. When the spectrum is narrow, it is found that nonlinearities can increase the frequency by as much as a factor of 2 for strong nonlinearities. It also is found that the qualitative features are not significantly changed by nonlinearities when the spectrum is narrow. These results confirm previous speculations by Hines that were based on heuristic arguments. It is also shown that nonlinear effects can be stronger when the spectrum is broad, in which case qualitative changes are possible.