The disclosed embodiments relate to a digital phase-locked loop (PLL) with dynamic gain control. This digital PLL includes a phase detector which receives a reference signal and a feedback signal as inputs and produces an output signal comprising up/down values. It also includes a digital loop filter which receives the phase-detector output signal as an input and produces an M-bit output signal. This digital loop filter is associated with a loop-parameter control unit (LPCU) which dynamically generates loop-filter parameters for the digital loop filter based on an observed pattern of up/down values from the phase-detector output over a specified period of time. A digitally controlled oscillator (DCO) receives the loop-filter output signal and produces a PLL output signal. Finally, a feedback path returns the PLL output signal to the phase detector.