Carbonation is the water-mediated replacement of silicate minerals, such as olivine, by carbonate, and is commonplace in the Earth's crust. This reaction can remove significant quantities of CO2 from the atmosphere and store it over geological timescales. Here we present the first direct evidence for CO2 sequestration and storage on Mars by mineral carbonation. Electron beam imaging and analysis show that olivine and a plagioclase feldspar-rich mesostasis in the Lafayette meteorite have been replaced by carbonate. The susceptibility of olivine to replacement was enhanced by the presence of smectite veins along which CO2-rich fluids gained access to grain interiors. Lafayette was partially carbonated during the Amazonian, when liquid water was available intermittently and atmospheric CO2 concentrations were close to their present-day values. Earlier in Mars' history, when the planet had a much thicker atmosphere and an active hydrosphere, carbonation is likely to have been an effective mechanism for sequestration of CO2.