Ion Coulomb crystals are currently establishing themselves as a highly controllable test-bed for mesoscopic systems of statistical mechanics. The detailed experimental interrogation of the dynamics of these crystals however remains an experimental challenge. In this work, we show how to extend the concepts of multi-dimensional nonlinear spectroscopy to the study of the dynamics of ion Coulomb crystals. The scheme we present can be realized with state-of-the-art technology and gives direct access to the dynamics, revealing nonlinear couplings even in the presence of thermal excitations. We illustrate the advantages of our proposal showing how two-dimensional spectroscopy can be used to detect signatures of a structural phase transition of the ion crystal, as well as resonant energy exchange between modes. Furthermore, we demonstrate in these examples how different decoherence mechanisms can be identified.