Early tuberization, a short period from stolon occurrence to tuber formation, is one of the major characteristics of a good early-maturing potato cultivar, while the regulatory mechanism of tuberization time (TT) is still unclear. In this study, two tetraploid cultivars, Zhongshu 3 (Z3) and Zhongshu 18 (Z18), with short and long TT respectively, were examined to reveal regulatory genes related to TT using RNA sequencing of tissue samples taken during stolon occurrence, stolon swelling and tuber formation. Cluster analysis showed that the gene expression patterns at the stolon swelling and tuber formation stages were significantly different from those at stolon occurrence in both Z3 and Z18. Therefore, we screened the differentially expressed genes (DEGs) at stolon swelling and tuber formation and compared them to those at stolon occurrence. A total of 3 085 DEGs were specifically identified and analyzed according to Gene Ontology and Kyoto Encyclopedia of Genes and Genomes enrichment, and DEGs involved in starch and sucrose metabolism, plant hormone signal transduction and plant circadian clock were significantly enriched. The circadian clock genes were significantly differentially expressed between Z3 and Z18, revealing an important role for the plant circadian pathway in regulating TT. Furthermore, three candidate genes, StGI, StPRR and StEFM involved in circadian regulation and significantly differentially expressed between Z3 and Z18, were discovered and confirmed by qRT-PCR. The results provide valuable information for understanding the regulatory mechanisms of potato TT and represent a step toward breeding early-maturing potato cultivars.