Enhanced ionic conductivity observed in a heteroepitaxial multilayer of yttria-stabilised zirconia and (YSZ) and strontium titanate (STO) has variously been attributed to lattice dilation or a disordered oxygen sublattice, leading to high interfacial mobility of anions, as compared to those of the constituent bulk oxides. We seek to understand the mechanism of ionic motion in such heterostructures by first simulating the atomic structure assuming coherent interfaces. After investigating possible low-energy interface structures using a genetic algorithm, we perform molecular dynamics simulations on these structures to examine the anionic diffusivity in the system. We find that the extreme biaxial tensile strain in the YSZ layer, as imposed between layers of STO, induces phases that differ from fluorite. The lowest energy structure is an unknown phase, which we refer to as quasi-cubic and whose cation sublattice resembles an extension of the perovskite; this structure does not lead to enhanced ionic conductivity, in contradiction to some reports in the literature.