The landscape of the north polar layered deposits of Mars (NPLD) is dominated by a pinwheel array of enigmatic spiral troughs. The troughs have intrigued planetary scientists since the Mariner 9 spacecraft returned the first close-up image in 1972, but conclusive evidence of their origin has remained elusive. Debate continues regarding all aspects of the troughs, including the possibility that they have migrated, their age in relation to the current NPLD surface, and whether they are fundamentally erosional or constructional features. The troughs are probably related to climatic processes, yet the nature of this relationship has remained a mystery. Previous data characterizing only the exposed NLPD surface were insufficient to test these hypotheses. Here we show that the central spiral troughs initiated after deposition of three-quarters of the NPLD, quickly reached a stable morphology and migrated approximately 65 kilometres poleward and 600 metres in altitude over the past two million years or so. Our radar stratigraphy rules out hypotheses of erosional incision post-dating deposition, and instead largely validates an early hypothesis for constructional trough migration with wind transport and atmospheric deposition as dominant processes. These results provide hard constraints for palaeo-climate models and a new context for evaluating imagery, spectral data, and now radar sounding data, the better to understand the link between orbital parameters and climate, the role of climate in shaping the polar ice of Mars, and eventually, the age of the polar deposits themselves.