Least squares sinusoid fit algorithm described in IEEE Standard for Digitizing Waveform Recorders (IEEE Std 1057): Algorithm for three-parameter and four-parameter least squares fit to sinewave data using matrix operations.

The algorithm is (in most cases) really quick. If the signal frequency is a guess, it has to be close to true frequency value.

For further information, consult IEEE Std 1057 and/or IEEE Std 1241 documentation.

Now also fits complex sinusoids i.e. phasors with noise and offset.

Here is an example with a regular sinusoid, which may be helpful:
t = 0:0.1:1000 ; % Time must be in seconds, not Matlab time
T = 10 ; % Period (s)
f = 1/T ; % Signal frequency (not sampling frequency!)
y = 2*sin(2*pi*t./T) ; % Sinusoid
[params, yest, yres, rmserr] = sinefit(y, t, f, 1, 1, 1) ;

The program worked fine for me it was exactly what I was looking for. I use it for the estimation of the SINAD and subsequent ENOB value. The method tends to shift more signal to the residual when the signal that is used gets longer.

Updates

18 Mar 2009

A minor bugfix in the plotting operation: now ALL samples are included in modulo-time plots.

18 Aug 2010

A feature update: added a possibility to fit non-iteratively.

26 Aug 2011

Improved iteration convergence: the accuracy for the initial frequency guess is more relaxed.

08 Sep 2011

Fixed a bug in input parameter handling (varargin behavior).

29 Jun 2012

A feature update: fitting extended to complex sinusoids.