The polar layered deposits of Mars demonstrate that thick accumulations of dust and ice deposits can develop on the planet if environmental conditions are favorable. These deposits appear to be hundreds of millions of years old, and other deposits of similar size but of greater age in nonpolar regions may have formed by similar processes. Possible relict dust deposits include, from oldest to youngest: Noachian intercrater materials, including Arabia mantle deposits, Noachian to Early Hesperian south polar pitted deposits, Early Hesperian Hellas and Argyre basin deposits, Late Hesperian Electris deposits, and the Amazonian Medusae Fossae Formation. These deposits typically are hundreds of meters to a couple kilometers thick and cover upward of a million or more square kilometers. The apparent persistence of dust sedimentation at the south pole back to the Early Hesperian or earlier and the early growth of Tharsis during the Late Noachian and perhaps earlier indicates that extensive polar wandering is unlikely following the Middle Noachian. A scenario for the overall history of dust and perhaps ice deposition on Mars includes widespread, voluminous accumulations perhaps planetwide during the Noachian as impacts, volcanism, and surface processes generated large amounts of dust; the Arabia deposits may have formed as ice availability and dust accumulation waned. During the Early Hesperian, thick dust sedimentation became restricted to the south pole and the deep Hellas and Argyre basins; the north polar sedimentary record prior to the Amazonian is largely obscured. Deposits at Electris and Medusae Fossae may have resulted from local sources of fine-grained material - perhaps volcanic eruptions.