The starting protection of large-scale rotating electrical machines under frequency conversion conditions is introduced. There are problems of insufficient anti-interference ability and large amount of calculation in the existing starting protection. Thus a recursive fixed frequency sampling variable data window discrete Fourier transform (FFSVDW-DFT) algorithm is proposed. The algorithm greatly reduces the amount of calculation but with calculation accuracy. First, the precise one-cycle data window length is calculated according to the system frequency, and then the recursive discrete Fourier transform algorithm is applied to calculate the magnitude of the phasor. When a fixed time elapses or the frequency changes, a non-recursive full-wave Fourier check is inserted to eliminate accumulated errors. Then, taking synchronous condenser starting protection under frequency conversion conditions as an example, the proposed recursive FFSVDW-DFT algorithm and the conventional peak algorithm are combined to improve starting protection. The improved protection is experimentally verified on the protection device. Experimental results show that the protection can accurately calculate the fundamental wave component in the fault at different system frequencies. In addition, the combination of the recursive FFSVDW-DFT and the peak algorithms can ensure the reliability of starting protection.