Collective cell migration is essential for both physiological and pathological processes. Adherens junctions (AJs) maintain the integrity of the migrating cell group and promote cell coordination while allowing cellular rearrangements. Here, we show that AJs undergo a continuous treadmilling along the lateral sides of adjacent leading cells. The treadmilling is driven by an actin-dependent rearward movement of AJs and is supported by the polarized recycling of N-cadherin. N-cadherin is mainly internalized at the cell rear and then recycled to the leading edge where it accumulates before being incorporated into forming AJs at the front of lateral cell-cell contacts. The polarized dynamics of AJs is controlled by a front-to-rear gradient of p120-catenin phosphorylation, which regulates polarized trafficking of N-cadherin. Perturbation of the GSK3-dependent phosphorylation of p120-catenin impacts on the stability of AJs, and the polarity and speed of leading cells during collective migration.