A system and method for calibrating a Voltage-Controlled Oscillator (VCO) having both fine-tuning control and coarse-tuning control. The VCO frequency can vary monotonically with changes in each of one or more operational conditions. The calibration method determines the coarse-tuning control setting for the VCO at system start-up. The method comprises generating frequency characterization data, generating a polynomial function from the characterization data, calculating the fine-tuning control voltage based on the polynomial function and a measurement of the operational conditions, and sweeping through ail the coarse-tuning control settings to determine the coarse-tuning control setting that generates the closest VCO frequency to a target frequency when using the calculated fine-tuning control voltage.