An accurate self-consistent way of coregistering the imaging and topographic data sets of the Mars Global Surveyor mission was developed and used to begin a stratigraphic analysis of the northern polar region. A distinct change in the layering style exists at a definite stratigraphic horizon near the base of the north polar layered deposits. Occurrences of the contact between two distinct layered units can be mapped hundreds of kilometers apart at nearly the same Mars Orbiter Laser Altimeter (MOLA) elevation. The lower layered unit has a consistent association with sand dunes, leading to the conclusion that it is an eroding sand-rich deposit that predates most of the overlying north polar layered deposits, which exhibits the expected features of a dust-ice mixture. These results suggest that an areally extensive erg was in existence before the present ice cap and that the present circumpolar erg is likely composed of material reworked from this older deposit. The volume of this lower unit is estimated to be on the order of 105 km3. The presence of this deposit implies that there existed a period in Mars' history when there was no icy polar cap. A dramatic climatic change leading to the deposition of the upper layered (icy) unit in the present-day polar layered deposits represents a major event in Mars' history. However, owing to uncertainties in the mechanics of layered deposits formation, such an event cannot be dated at this time.