The total amount of carbon in the atmosphere, oceans and other near-surface reservoirs is thought to be negligible compared to that stored in the Earth's mantle. Although the mode of carbon storage in the mantle is largely unknown, observations of microbubbles on dislocations in minerals from mantle xenoliths has led to the suggestion that carbon may be soluble in silicates at high pressure. Here we report measurements of carbon solubility in olivine, the major constituent of the upper mantle, at pressures up to 3.5 GPa. We have found that, contrary to previous expectations, carbon solubility in olivine is exceedingly low--of the order of 0.1 to 1 parts per million by weight. Together with similar data for pyroxenes, garnet and spinel, we interpret this to imply that most carbon must be present as a separate phase in the deeper parts of the upper mantle, probably as a carbonate phase. Large-scale volcanic eruptions tapping such a carbonate-bearing mantle reservoir might therefore rapidly transfer large amounts of carbon dioxide into the atmosphere, consistent with models that link global mass extinctions to flood basalt eruptions via a sudden increase in atmospheric carbon dioxide levels.