Novel melilite-type gallium-oxides are attracting attention as promising new oxide-ion conductors with potential use in clean energy devices such as solid oxide fuel cells. Here, an atomic-scale investigation of the LaSrGa3O7-based system using advanced simulation techniques provides valuable insights into the defect chemistry and oxide ion conduction mechanisms, and includes comparison with the available experimental data. The simulation model reproduces the observed complex structure composed of layers of corner-sharing GaO4 tetrahedra. A major finding is the first indication that oxide-ion conduction in La(1.5)4Sr(0.46)Ga(3)O(7.27) occurs through an interstitialcy or cooperative-type mechanism involving the concerted knock-on motion of interstitial and lattice oxide ions. A key feature for the transport mechanism and high ionic conductivity is the intrinsic flexibility of the structure, which allows considerable local relaxation and changes in Ga coordination.