Mars has a thin (6 mbar) CO2 atmosphere currently. There is strong evidence for paleolakes and rivers formed by warm climates on Mars, including after 3.5 billion years (Ga) ago, which indicates that a CO2 atmosphere thick enough to permit a warm climate was present at these times. Since Mars no longer has a thick CO2 atmosphere, it must have been lost. One possibility is that Martian CO2 was lost to space. Oxygen escape rates from Mars are high enough to account for loss of a thick CO2 atmosphere, if CO2 was the main source of escaping O. But here, using H isotope ratios, O escape calculations, and quantification of the surface O sinks on Mars, we show for the first time that O escape from Mars after 3.5 Ga must have been predominantly associated with the loss of H2O, not CO2, and therefore it is unlikely that >250 mbar Martian CO2 has been lost to space in the last 3.5 Ga, because such results require highly unfavored O loss scenarios. It is possible that the presence of young rivers and lakes on Mars could be reconciled with limited CO2 loss to space if crater chronologies on Mars are sufficiently incorrect that all apparently young rivers and lakes are actually older than 3.5 Ga, or if climate solutions exist for sustained runoff on Mars with atmospheric CO2 pressure <250 mbar. However, our preferred solution to reconcile the presence of <3.5 Gya rivers and lakes on Mars with the limited potential for CO2 loss to space is a large, as yet undiscovered, geological C sink on Mars.