An all-digital phase-locked loop (ADPLL) and a calibration method thereof are provided. The ADPLL includes a digitally controlled oscillator (DCO), a time-to-digital converter (TDC) coupled to the DCO, and a normalization circuit coupled to the TDC. The TDC is configured to generate a clock signal according to a frequency control signal. The TDC is configured to generate a digital output signal according to a phase difference between the clock signal and a reference signal. The normalization circuit is configured to convert the digital output signal into a clock phase value according to a gain parameter. The normalization circuit selects one of a plurality of candidate gain parameters stored in the normalization circuit in response to the digital output signal, for being utilized as the gain parameter.