A Phase-Locked Loop (PLL) has a multi-curve voltage-controlled oscillator (VCO) with a curve-select input that adjusts the capacitance within the VCO and thus the VCO gain. A calibration unit generates a curve-select value to the VCO. Coarse calibration selects a Center Curve CC value using binary search of the curve-select bits. During fine calibration, the number of pulses of the VCO output are counted and stored for all curves in a target window around the center curve. The stored pulse counts are compared to an ideal pulse count for a specified frequency, and the curve-select value for the closest-matching pulse count is applied to the VCO. The target window is much smaller than all possible curves, so calibration is performed only on a few curves, reducing calibration time. A switch before the VCO opens the loop for faster open-loop calibration. Pulses are counted digitally without expensive analog comparators.