The concentrations and locations of elements that strongly partition into the fluid phase in rocks provide essential constraints on geochemical and geodynamical processes in Earth's interior. A fundamental question remains, however, as to where these incompatible elements reside before formation of the fluid phase. Here we show that partitioning of calcium between the grain interiors and grain boundaries of olivine in natural and synthetic olivine-rich aggregates follows a thermodynamic model for equilibrium grain-boundary segregation. The model predicts that grain boundaries can be the primary storage sites for elements with large ionic radius--that is, incompatible elements in the Earth's mantle. This observation provides a mechanism for the selective extraction of these elements and gives a framework for interpreting geochemical signatures in mantle rocks.