Experience with the maximum entropy spectral analysis (MESA) method suggests that (1) it can produce inaccurate frequency estimates of short sample sinusoidal data, and (2) it sometimes produces calculated values for the filter coefficients that are unduly contaminated by rounding errors. Consequently, in this report we develop an algorithm for solving the underlying least-squares linear prediction (LSLP) problem directly, without forcing a Toeplitz structure on the model. This approach leads to more accurate frequency determination for short sample harmonic processes, and our algorithm is computationally efficient and numerically stable. The algorithm can also be applied to two other versions of the linear prediction problem. A Fortran program is given in Part II.