Voltage controlled oscillator (VCO) gain tracking is used for programming modulation gain settings to minimize modulation distortion in a phase locked loop of a mobile station (10). A synthesizer (20) generates a tuning voltage (Vt) for controlling a frequency of a (VCO) modulated radio frequency signal. A controller (22) outputs a modulation data signal and includes an ADC (72) for receiving the tuning voltage from the synthesizer (20) on a VCO feedback loop (70), a gain control lookup table (LUT) (76) for storing gain setting calibration data for respective mobile station sub-bands, and a gain setting (DAC) (78) for outputting a modulation gain control signal to the synthesizer (20). The modulation gain setting calibration data is calibrated using a one-time or continuous calibration methodlogy during, respectively, a background or normal mode of operation.