We describe Castalia, a proposed mission to rendezvous with a Main Belt Comet (MBC), 133P/Elst-Pizarro. MBCs are a recently discovered population of apparently icy bodies within the main asteroid belt between Mars and Jupiter, which may represent the remnants of the population which supplied the early Earth with water. Castalia will perform the first exploration of this population by characterising 133P in detail, solving the puzzle of the MBC's activity, and making the first in situ measurements of water in the asteroid belt. In many ways a successor to ESA's highly successful Rosetta mission, Castalia will allow direct comparison between very different classes of comet, including measuring critical isotope ratios, plasma and dust properties. It will also feature the first radar system to visit a minor body, mapping the ice in the interior. Castalia was proposed, in slightly different versions, to the ESA M4 and M5 calls within the Cosmic Vision programme. We describe the science motivation for the mission, the measurements required to achieve the scientific goals, and the proposed instrument payload and spacecraft to achieve these.