We present an improved method for estimating the frequency‐dependent phase velocity of ambient noise cross spectra by waveform fitting of Aki’s formula (Aki, 1957). The key part of the procedure is the use of a grid search to generate an initial estimate of the phase velocity that matches the observed cross spectrum without any cycle slips. A generalized least‐squares procedure is then used to refine this initial estimate. The grid search has only three frequency nodes, at the left end, center, and right end of the frequency band of interest, but parameterizes velocity finely, with 40 increments at each of these nodes. Trial phase velocity curves are generated by linear interpolation between nodes, and the curve that best predicts the observed cross spectrum is chosen as the initial estimate. The generalized least‐squares refinement implements two types of prior information: the phase velocity is close to a smoothed version of the initial estimate, and the phase velocity varies smoothly with frequency. In addition to estimating the frequency‐dependent phase velocity function, the method provides its variance and resolution. The method is robust to low signal‐to‐noise levels and so may prove especially attractive in cases in which short array‐deployment times limit the quality of cross‐spectral estimates. It also provides useful estimates at short interstation distance, when the cross spectrum has few zero crossings.