Phase-modulated wave packet interferometry is combined with mass-resolved photoion detection to investigate rubidium atoms attached to helium nanodroplets in a molecular beam experiment. The spectra of atomic Rb electronic states show a vastly enhanced sensitivity and spectral resolution when compared to conventional pump–probe wave packet interferometry. Furthermore, the formation of Rb*He exciplex molecules is probed and for the first time a fully resolved vibrational spectrum for transitions between the lowest excited 5Π3/2 and the high-lying electronic states 22Π, 42Δ, 62Σ is obtained and compared to theory. The feasibility of applying coherent multidimensional spectroscopy to dilute cold gas phase samples is demonstrated in these experiments.