In this work, we have discovered Ca3Ga4O9 as a rare-earth-free oxide-ion conductor by a combined technique of bond valence (BV)-based energy calculations, synthesis, and characterization of structural and transport properties. Here, the energy barriers for oxide-ion migration (E-b) of 217 Ga-containing oxides were calculated by the BV method to screen the candidate materials of oxide-ion conductors. We chose the orthorhombic calcium gallate Ca3Ga4O9 as a candidate of oxide-ion conductors, because Ca3Ga4O9 had a relatively low E-b. Ca3Ga4O9 was synthesized by a solid-state-reaction method. Rietveld analyses of time-of-flight neutron and synchrotron X-ray powder diffraction data of Ca3Ga4O9 indicated an orthorhombic Cmm2 layered crystal structure consisting of Ca-18 and (Ga4O9)(6) units where the (Ga4O9)(6) units form the two-dimensional (2D) corner-sharing GaO4 tetrahedral network. The electromotive force measurements with an oxygen concentration cell showed that the transport numbers of the oxide ion were 0.69 at 1073 K and 0.84 at 973 K in Ca3Ga4O9, which indicates that the major carrier of Ca3Ga4O9 is the oxide ion. The oxide-ion conductivity was estimated to be 1.03(8) x 10(-5) S cm(-1) at 1073 K. The total electrical conductivity and impedance spectroscopy measurements of this Ca3Ga4O9 sample indicated that the bulk conductivity was much higher than the grain-boundary conductivity and that the total conductivity was equivalent to the bulk conductivity. The bond valence-based energy landscape calculated using the refined crystal parameters of Ca3Ga4O9 indicated 2D oxide-ion diffusion in the layered tetrahedral network [(Ga4O9)(6) unit]. It was found that the structural and transport properties of Ca3Ga4O9 are similar to those of LaSrGa3O7 melilite.