The early stages of planetary differentiation are characterized by the formation of magma oceans, which crystallize from the base up. The final, iron-rich residues of crystallization are dense and therefore tend to sink into the mantle, whereas the deeper, magnesium-rich material tends to rise up. The resultant mantle overturn would have had a profound influence on the evolution of the planets. Such an event probably occurred on Mars, but its initiation, timing and geochemical consequences are poorly constrained. Here we use isotopic data for nakhlite meteoriteschunks of martian crust transported to the Earthand numerical simulations to constrain the evolution of the early martian mantle. We interpret the isotopic composition of the meteorites as evidence for an episode that occurred relatively early in Mars history, about 100 million years after the planets formation, during which garnet was removed from material that rose up from the deep mantle. This episode implies large-scale reorganization in the martian mantle and thereby provides compelling support for overturn. We suggest that this event probably led to substantial re-melting in the deepest mantle, which may have influenced early martian processes such as the development of crustal dichotomy.