The search for electrolyte materials with high oxygen conductivities is a key step toward reducing the operation temperature of fuel cells, which is currently above 700 degrees C. We report a high lateral ionic conductivity, showing up to eight orders of magnitude enhancement near room temperature, in yttria-stabilized zirconia (YSZ)/strontium titanate epitaxial heterostructures. The enhancement of the conductivity is observed, along with a YSZ layer thickness-independent conductance, showing that it is an interface process. We propose that the atomic reconstruction at the interface between highly dissimilar structures (such as fluorite and perovskite) provides both a large number of carriers and a high-mobility plane, yielding colossal values of the ionic conductivity.