An advanced spatial-carrier phase-shifting (SCPS) algorithm based on least-squares iterative procedure is proposed to cope with the errors caused by the uncertainty of spatial carrier frequency. The algorithm divides the randomly spatial carrier interferogram into four randomly phase-shifted interferograms and then obtains the phase distributions by a least-squares iterative procedure. The algorithm provides stable and fast convergence, high spatial frequency resolution and accurate phase extraction with only one single randomly spatial carrier interferogram. The results of computer simulation and experiment show that the accuracy is better than λ/20 (peak value, PV) and λ/200 (root mean square, RMS) with about 10 times iterations and it is better than that obtained by the fast Fourier transform (FFT) algorithm. Computer simulations also show that the accuracy of the algorithm can be improved by increasing the spatial carrier frequency and making the direction of the carrier near 45° or 135°.