©2016. The Authors. What allows a planet to be both within a potentially habitable zone and sustain habitability over long geologic time? With the advent of exoplanetary astronomy and the ongoing discovery of terrestrial-type planets around other stars, our own solar system becomes a key testing ground for ideas about what factors control planetary evolution. Mars provides the solar system's longest record of the interplay of the physical and chemical processes relevant to habitability on an accessible rocky planet with an atmosphere and hydrosphere. Here we review current understanding and update the timeline of key processes in early Mars history. We then draw on knowledge of exoplanets and the other solar system terrestrial planets to identify six broad questions of high importance to the development and sustaining of habitability (unprioritized): (1) Is small planetary size fatal? (2) How do magnetic fields influence atmospheric evolution? (3) To what extent does starting composition dictate subsequent evolution, including redox processes and the availability of water and organics? (4) Does early impact bombardment have a net deleterious or beneficial influence? (5) How do planetary climates respond to stellar evolution, e.g., sustaining early liquid water in spite of a faint young Sun? (6) How important are the timescales of climate forcing and their dynamical drivers? Finally, we suggest crucial types of Mars measurements (unprioritized) to address these questions: (1) in situ petrology at multiple units/sites; (2) continued quantification of volatile reservoirs and new isotopic measurements of H, C, N, O, S, Cl, and noble gases in rocks that sample multiple stratigraphic sections; (3) radiometric age dating of units in stratigraphic sections and from key volcanic and impact units; (4) higher-resolution measurements of heat flux, subsurface structure, and magnetic field anomalies coupled with absolute age dating. Understanding the evolution of early Mars will feed forward to understanding the factors driving the divergent evolutionary paths of the Earth, Venus, and thousands of small rocky extrasolar planets yet to be discovered.