Triple ionic-electronic conductors, capable of concurrent conduction of protons, oxygen ions, and electrons, are promising cathodes in ceramic fuel cells. Though thoroughly studied, extensive evaluation and explanation of their transport phenomena are crucial for guiding future research. In this work, the structure, composition, and formation enthalpies of BaCo0.4Fe0.4Zr0.2−XYXO3−δ (BCFZYX, X = 0, 0.05, 0.1, 0.15, 0.2) are correlated with its trends in defect mobility. Three compositions of BCFZYX, X = 0, 0.1, 0.2, are measured under X-ray diffraction and neutron powder diffraction to reveal a common cubic perovskite structure with increasing oxygen vacancy concentration upon increasing yttrium concentration. Formation enthalpies obtained by high-temperature calorimetry reveal a general destabilization of this perovskite structure with yttrium substitution, with deviations at the endmember compositions. Further analysis suggests that high yttrium substitution causes yttrium-vacancy pairs to be more energetically favorable than randomized oxygen vacancies. This phenomenon, along with changes in oxygen vacancy concentration, helps explain observed trends in oxygen-ion and proton mobility in the compositional suite as well as criteria for the selection of high performing, durable protonic ceramic fuel cell materials.