The polar layered deposits of Mars contain the planet’s largest known reservoir of water ice^1,2 and the prospect of revealing a detailed Martian palaeoclimate record^3,4, but the mechanisms responsible for the formation of the dominant features of the north polar layered deposits (NPLD) are unclear, despite decades of debate. Stratigraphic analyses of the exposed portions of Chasma Boreale—a large canyon 500 km long, up to 100 km wide, and nearly 2 km deep—have led most researchers to favour an erosional process for its formation following initial NPLD accumulation. Candidate mechanisms include the catastrophic outburst of water⁵, protracted basal melting⁶, erosional undercutting⁷, aeolian downcutting^7,8,9 and a combination of these processes¹⁰. Here we use new data from the Mars Reconnaissance Orbiter to show that Chasma Boreale is instead a long-lived, complex feature resulting primarily from non-uniform accumulation of the NPLD. The initial valley that later became Chasma Boreale was matched by a second, equally large valley that was completely filled in by subsequent deposition, leaving no evidence on the surface to indicate its former presence. We further demonstrate that topography existing before the NPLD began accumulating influenced successive episodes of deposition and erosion, resulting in most of the present-day topography. Long-term and large-scale patterns of mass balance achieved through sedimentary processes, rather than catastrophic events, ice flow or highly focused erosion, have produced the largest geomorphic anomaly in the north polar ice of Mars.