Adaptive multi-band frequency calibration is provided for a phase-locked loop (PLL). A voltage controller oscillator (VCO) is initially selected nominally associated with first synthesized signal frequency, where the VCO is selected from a plurality of n VCOs, and each VCO is tunable across a band of synthesized signal frequencies. A lock detector compares a nominal first synthesized signal frequency to a reference signal frequency. In response to sensing a difference between the nominal first synthesizer and reference signal frequencies, an out-of-lock condition is asserted and a VCO is reselected from the plurality of n VCOs. A mid-point control voltage is supplied to a control voltage input of the reselected VCO. A difference is measured between a mid-point synthesized signal frequency and the reference signal frequency. If the difference is less than a first threshold, the reselected VCO is assigned to generate the first synthesized signal frequency.