Core formation on the Earth and Mars involved the physical separation of metal and silicate, most probably in deep magma oceans. Although core-formation models explain many aspects of mantle geochemistry, they have not accounted for the large differences observed between the compositions of the mantles of the Earth (approximately 8 wt% FeO) and Mars (approximately 18 wt% FeO) or the smaller mass fraction of the martian core. Here we explain these differences as a consequence of the solubility of oxygen in liquid iron-alloy increasing with increasing temperature. We assume that the Earth and Mars both accreted from oxidized chondritic material. In a terrestrial magma ocean, 1,200-2,000 km deep, high temperatures resulted in the extraction of FeO from the silicate magma ocean owing to high solubility of oxygen in the metal. Lower temperatures of a martian magma ocean resulted in little or no extraction of FeO from the mantle, which thus remains FeO-rich. The FeO extracted from the Earth's magma ocean may have contributed to chemical heterogeneities in the lowermost mantle, a FeO-rich D" layer and the light element budget of the core.