The ancient cratered terrain of the southern highlands of Mars is thought to hold clues to the planet's early differentiation, but until now no meteoritic regolith breccias have been recovered from Mars. Here we show that the meteorite Northwest Africa (NWA) 7533 (paired with meteorite NWA 7034) is a polymict breccia consisting of a fine-grained interclast matrix containing clasts of igneous-textured rocks and fine-grained clast-laden impact melt rocks. High abundances of meteoritic siderophiles (for example nickel and iridium) found throughout the rock reach a level in the fine-grained portions equivalent to 5 per cent CI chondritic input, which is comparable to the highest levels found in lunar breccias. Furthermore, analyses of three leucocratic monzonite clasts show a correlation between nickel, iridium and magnesium consistent with differentiation from impact melts. Compositionally, all the fine-grained material is alkalic basalt, chemically identical (except for sulphur, chlorine and zinc) to soils from Gusev crater. Thus, we propose that NWA 7533 is a Martian regolith breccia. It contains zircons for which we measured an age of 4,428 ± 25 million years, which were later disturbed 1,712 ± 85 million years ago. This evidence for early crustal differentiation implies that the Martian crust, and its volatile inventory, formed in about the first 100 million years of Martian history, coeval with earliest crust formation on the Moon and the Earth. In addition, incompatible element abundances in clast-laden impact melt rocks and interclast matrix provide a geochemical estimate of the average thickness of the Martian crust (50 kilometres) comparable to that estimated geophysically.