Exploration of the Ca-Ga-Nb-O phase diagram by solid-state reaction in air led to isolation of Ca4GaNbO8. The crystal structure was determined ab initio by synchrotron X-ray and high-resolution neutron powder diffraction. Ca4GaNbO8 adopts a heavily distorted oxygen-deficient perovskite structure with the rare feature of complete ordering of the three B-site cations, driven by their distinct chemistries. One of the calcium cations occupies a distorted octahedral cavity and together with tetrahedrally coordinated Ga and octahedrally coordinated Nb is considered as a B-site cation in the ABO(3-x) perovskite. This interpretation of the structure reveals Ca4GaNbO8 is part of a family of B-site and vacancy-ordered perovskites related to mineral structures. The anion-vacancy ordering pattern in Ca4GaNbO8 is driven by the coordination preferences of the three structurally distinct cations and correlated with the ordering of each cation on a distinct site. Alternating current impedance spectra show Ca4GaNbO8 is insulating (bulk conductivity 10(-5)-10(-7) S.cm(-1)) over the measured temperature range 550-950 degrees C with an activation energy of 1.10(3) eV.