Commonly, the frequency shift of back-reflection spectra is the key parameter to measure quantitatively local temperature or strain changes in frequency-scanned Rayleigh-based distributed fiber sensors. Cross-correlation is the most common method to estimate the frequency shift; however, large errors may take place, particularly when the frequency shift introduced by the temperature or strain change applied to the fiber is beyond the spectral width of the main correlation peak. This fact substantially limits the reliability of the system, and therefore requires careful analysis and possible solutions. In this paper, an analytical model is proposed to thoroughly describe the probability of large errors. This model shows that the cross-correlation intrinsically and inevitably leads to large errors when the sampled signal distribution is finite, even under perfect signal-to-noise ratio. As an alternative solution to overcome such a problem, least mean squares is employed to estimate the frequency shift. In addition to reducing the probability of large errors, the proposed method only requires to measure a narrow spectrum, significantly reducing the measurement time compared to state-of-the-art implementations. Both the model and the solution are experimentally verified using a frequency-scanned phase-sensitive optical time-domain reflectometry ( $\varphi$ -OTDR) system, achieving a spatial resolution of 5 cm, with a sensing range of 860 m and an acquisition time below 15 s, over a measurable temperature range of more than 100 K with a repeatability of 20 mK, corresponding to a temperature dynamic range of 5000 resolved points.