In this paper, the frequency control loop performance of nonlinear microelectromechanical resonators is investigated. A phase-locked loop (PLL) controller is used to track the resonance frequency of a nonlinear resonator and to compensate for the changes in the natural frequency. Based on the harmonic balance approach, governing equations of the dynamics of a nonlinear resonator are obtained, and using the mathematical model of the PLL, a new stability criterion for the closed-loop system is proposed. The relationship between the amplitude of the external driving force command and the stability of the control loop is elaborated for both hardening and softening nonlinearities. A nonlinear gain control strategy is proposed for the frequency-tracking loop, and its effectiveness is shown through simulation studies.