High-conductivity oxide ion electrolytes are needed to reduce the operating temperature of solid-oxide fuel cells. Oxide mobility in solids is associated with defects. Although anion vacancies are the charge carriers in most cases, excess (interstitial) oxide anions give high conductivities in isolated polyhedral anion structures such as the apatites. The development of new families of interstitial oxide conductors with less restrictive structural constraints requires an understanding of the mechanisms enabling both incorporation and mobility of the excess oxide. Here, we show how the two-dimensionally connected tetrahedral gallium oxide network in the melilite structure La(1.54)Sr(0.46)Ga(3)O(7.27) stabilizes oxygen interstitials by local relaxation around them, affording an oxide ion conductivity of 0.02-0.1 S cm(-1) over the 600-900 degrees C temperature range. Polyhedral frameworks with central elements exhibiting variable coordination number can have the flexibility needed to accommodate mobile interstitial oxide ions if non-bridging oxides are present to favour cooperative network distortions.