A phase-locked loop circuit using a multi-curve voltage-controlled oscillator (VCO) having a set of operating curves, each operating curve corresponding to a different frequency range over a control voltage range. The phase-locked loop circuit includes a phase and frequency detector driving a charge pump and a digital control circuit configured to perform a closed loop curve search operation to select one of the operating curves in the multi-curve VCO and to perform a curve tracking operation using the selected operating curve, the selected operating curve being used by the VCO to generate an output signal with an output frequency being equal or close to a target frequency of the phase-locked loop. In one embodiment, the digital control circuit increases the charge pump current above a nominal current value during the closed loop curve search operation and set the charge pump current to the nominal current during the curve tracking operation.