The impact heat accumulated during the late stage of planetary accretion can melt a significant part or even the entire mantle of a terrestrial body, giving rise to a global magma ocean. [...] Assuming fractional crystallization of the magma ocean, dense cumulates are produced close to the surface, largely due to iron enrichment in the evolving magma ocean liquid (Elkins-Tanton et al., 2003). A gravitationally unstable mantle thus forms, which is prone to overturn. We investigate the cumulate overturn and its influence on the thermal evolution of Mars using mantle convection simulations in 2D cylindrical geometry. We present a suite of simulations using different initial conditions and a strongly temperature-dependent viscosity. We assume that all radiogenic heat sources have been enriched during the freezing-phase of the magma ocean in the uppermost 50 km and that the initial steam-atmosphere created by the degassing of the freezing magma ocean was rapidly lost, implying that the surface temperature is set to present-day values. In this case, a stagnant lid forms rapidly on top of the convective interior preventing the uppermost dense cumulates to sink, even when allowing for a plastic yielding mechanism. Below this dense stagnant lid, the mantle chemical gradient settles to a stable configuration. The convection pattern is dominated by small-scale structures, which are difficult to reconcile with the large-scale volcanic features observed over Mars surface and partial melting ceases in less than 900 Ma. Assuming that the stagnant lid can break because of additional mechanisms and allowing the uppermost dense layer to overturn, a stable density gradient is obtained, with the densest material and the entire amount of heat sources lying above the CMB. This stratification leads to a strong overheating of the lowermost mantle [...]