Oxide ionic conductors typically operate at high temperatures, which limits their usefulness. Colossal room-temperature ionic conductivity was recently discovered in multilayers of yttria-stabilized zirconia (YSZ) and SrTiO3. Here we report density-functional calculations that trace the origin of the effect to a combination of lattice-mismatch strain and O-sublattice incompatibility. Strain alone in bulk YSZ enhances O mobility at high temperatures by inducing extreme O disorder. In multilayer structures, O-sublattice incompatibility causes the same extreme disorder at room temperature.