jats:pVertically aligned nanocomposite (VAN) films have self-assembled pillar-matrix nanostructures. Owing to their large area-to-volume ratios, interfaces in VAN films are expected to play key roles in inducing functional properties, but our understanding is hindered by limited knowledge about their structures. Motivated by the lack of definitive explanation for the experimentally found enhanced ionic conductivity in Sm-doped-CeO2/SrTiO3 VAN films, we determine the structure at vertical interfaces using random structure searching and explore how it can affect ionic conduction. Interatomic potentials are used to perform the initial searching, followed by first-principles calculations for refinement. Previously unknown structures are found, with lower energy than that of an optimized hand-built model. We find a strongly distorted oxygen sublattice which gives a complex landscape of vacancy energies. The cation lattice remains similar to the bulk phase, but has a localized strain field. The excess energy of the interface is similar to that of high angle grain boundaries in SrTiO3.</jats:p>