We have discovered a high oxide ion conductor within the perovskite-type (Ba1-x-ySrxLay)InO2.5+y/2 solid-solution system. The system was derived from brownmillerite-type Ba2In2O5, which possessed a ordered oxide ion vacancies. When we doped La3+ into the Ba site, the vacancy changed to a disordered state. The oxide ion conductivity increased with the amount of doped La3+, reaching a maximum value of 0.12 (S/cm) at 800 oC in (Ba0.3Sr0.2La0.5)InO2.75, a level exceeding that of yttria-stabilized zirconia. The oxide ion conductivity of this system was strongly dependent on the unit cell free volume, which appears to be the key parameter governing oxide ion mobility.