The existence of new compounds is often postulated by solid state chemists by replacing an ion in the crystal structure of a known compound by a chemically similar ion. In this work, we present how this new compound discovery process through ionic substitutions can be formulated in a mathematical framework. We propose a probabilistic model assessing the likelihood for ionic species to substitute for each other while retaining the crystal structure. This model is trained on an experimental database of crystal structures, and can be used to quantitatively suggest novel compounds and their structures. The predictive power of the model is demonstrated using cross-validation on quaternary ionic compounds. The different substitution rules embedded in the model are analyzed and compared to some of the traditional rules used by solid state chemists to propose new compounds (e.g., ionic size).