The approximately 2 km thick north polar layered deposits (NPLD) are often considered to contain the most complete and detailed stratigraphic records of recent climate of Mars. Exposures of the dense layering within troughs and scarps allowed detailed reconstructions of the latest accumulation history of these water ice deposits, but we lack knowledge of their initial emplacement. The Shallow Radar (SHARAD) onboard Mars Reconnaissance Orbiter (MRO) penetrates the NPLD to their base and detects their internal layering, overcoming the limitation of scarce and scattered visible outcrops of the lowermost sequences. In this study, we map reflectors in SHARAD data that result from discrete stratigraphic horizons in order to delineate the three-dimensional stratigraphy of the lowermost ∼500 m NPLD sequence and reconstruct their accumulation history. We confirm the large-scale lateral continuity and thickness uniformity of the deposits previously detected within the lowermost NPLD. However, stratigraphic complexity—in the form of pinch-outs and significant thickness variations—arises when we examine single radar units. We find evidence of an initially limited geographic stability of water ice within two deposits that are centered at the North Pole and present-day Gemina Lingula. A period of lateral ice sheet growth followed, interrupted only once by a retreat episode. Lower net accumulation is observed on pre-existing slopes, suggesting a reduction of water ice stability due to increased solar radiation incidence and/or transport by katabatic winds. Lateral transport of water ice by wind is also suggested by thickness undulations toward the top of the sequence, resembling cyclic steps. Water ice accumulation models based on orbital forcing predict a sequence of deposition and retreat events that is generally compatible with our reconstructed accumulation history. Therefore, we interpret the stratigraphic complexity that we observe as regional and, possibly global, climate change induced by orbital forcing. We also find that at least two units are completely buried within the NPLD and do not outcrop, and that NPLD deposition in some places was contemporaneous with deposition of the stratigraphically underlying cavi unit in other places. Both of these findings show that radar reflector mapping is a necessary complement to any stratigraphic reconstruction based on visible exposures.