A new algorithm for estimating the fundamental frequency of power system signals is presented. The proposed algorithm consists of two stages: orthogonal decomposition and a complex Prony analysis. First, the input signal is decomposed into two orthogonal components using cosine and sine filters, and a variable window is adapted to enhance the performance of eliminating harmonics. Then a complex Prony analysis that is proposed in this paper is used to estimate the fundamental frequency by approximating the cosine-filtered and sine-filtered signals simultaneously. To evaluate the performance of the algorithm, amplitude modulation and harmonic tests were performed using simulated test signals. The performance of the algorithm was also assessed for dynamic conditions on a single-machine power system. The Electromagnetic Transients Program was used to generate voltage signals for a load increase and single phase-to-ground faults. The performance evaluation showed that the proposed algorithm accurately estimated the fundamental frequency of power system signals in the presence of amplitude modulation and harmonics.