Mars and Earth are the only two planets known to have long histories of dynamical cycling of water through their atmosphere, lithosphere, and cryosphere. Although we have known for thirty years that Mars had an early history with aqueous activity on its surface, exciting new results from current Mars missions are only now revealing the extensive sedimentary evidence of that history. Early Mars had extensive lakes and probably transient seas that were associated with a climate capable of generating the precipitation and runoff to sculpt its landscape and fill sedimentary basins. Well-preserved fluvial deltas show that early Mars was surprisingly Earthlike in its geological processes. The immense quantity of water implied for sequestering in the Martian permafrost (as ground ice) and beneath it (as ground water) requires an explanation as to the history of water recycling. These and other anomalous aspects of Martian geology are explained by a theory that incorporates the onset and termination of a core dynamo, associated with an early regime of plate tectonics during the first few hundred million years of the planet's history. Rapid accretion of thickened continental crust, as modified by concurrent high impacting rates, volcanism, and denudation, ultimately resulted in the southern highlands. Following cessation of the dynamo, the plate-tectonic regime terminated with zones of focused subduction in the Tharsis and Elysium areas. The resulting high concentration of water and other volatiles in the Martian deep mantle led to the Tharsis and Elysium superplumes, the long-term persistence of which is responsible-for much of the volcanism, tectonism, water outbursts, and climate change that mark the subsequent, 4 billion year geological history of Mars.