The formation of a primordial crust is a critical step in the evolution of terrestrial planets but the timing of this process is poorly understood. The mineral zircon is a powerful tool for constraining crust formation as it can be accurately dated with the U-Pb system and is resistant to subsequent alteration. Moreover, the high concentration of Hf in zircon allow for the utilization of the 176Lu- 176Hf decay system to determine the nature and formation timescale of its source reservoir 1– 3. Ancient igneous zircons with ages of ~4430 Ma have been reported in martian meteorites believed to represent regolith breccias from the southern highlands of Mars 4, 5. These zircons are present in evolved lithologies interpreted to reflect re-melted primary martian crust 4 thereby potentially providing unique insights into early crustal evolution on Mars. Here, we report concomitant high-precision U-Pb ages and Hf-isotope compositions of ancient zircons from the NWA 7034 martian regolith breccia. Seven zircons with mostly concordant U-Pb ages define 207Pb/ 206Pb dates ranging from 4476.3±0.9 Ma to 4429.7±1.0 Ma, including the oldest directly dated material from Mars. All zircons record unradiogenic initial Hf-isotope compositions inherited from an enriched, andesitic-like crust extracted from a primitive mantle no later than 4547 Ma. Thus, a primordial crust existed on Mars by this time and survived for ~100 Myr before it was reworked, possibly by impacts 4, 5, to produce magmas from which the zircons crystallized. Given that formation of a stable primordial crust is the end product of planetary differentiation, our data require that the accretion, core formation and magma ocean crystallization on Mars was completed <20 Myr after Solar System formation. These timescales support models suggesting rapid magma ocean crystallization leading to a gravitationally unstable stratified mantle, which subsequently overturns resulting in decompression melting of rising cumulates and extraction of a primordial basaltic to andesitic crust 6, 7.