This paper presents a varactor-based all-digital phase-locked loop (ADPLL) with a multi-phase digitally controlled oscillator (DCO) for near-threshold voltage operation. In addition, a new all-digital reference spur suppression (RSS) circuit with multiple phases random-sampling techniques to effectively spread the reference clock frequency is proposed to randomize the synchronized DCO register behavior and reduce the reference spur. Because the equivalent reference clock frequency is reserved, the loop behavior is maintained. The area of the proposed spur suppression circuit is only 4.9% of the ADPLL (0.038 mm2). To work reliably at the near-threshold region, a multi-phase DCO with NMOS varactors is presented to acquire precise frequency resolution and high linearity. In the near-threshold region (VDD =0.52 V), the ADPLL only dissipates 269.9 μW at 100 MHz output frequency. It has a reference spur of -52.2 dBc at 100 MHz output clock frequency when the spur suppression circuit is deactivated. When the spur suppression circuit is activated, the ADPLL shows a reference spur of -57.3 dBc with the period jitter of 0.217% UI.