Vertically aligned nanocomposite (VAN) films, comprising nanopillars of one phase embedded in a matrix of another, have shown great promise for a range of applications due to their high interfacial areas oriented perpendicular to the substrate. In particular, oxide VANs show enhanced oxide-ion conductivity in directions that are orthogonal to those found in more conventional thin-film heterostructures; however, the structure of the interfaces and its influence on conductivity remain unclear. In this work, 17O NMR spectroscopy is used to study CeO2-SrTiO3 VAN thin films: selective isotopic enrichment is combined with a lift-off technique to remove the substrate, facilitating detection of the 17O NMR signal from single atomic layer interfaces. By performing the isotopic enrichment at variable temperatures, the superior oxide-ion conductivity of the VAN films compared to the bulk materials is shown to arise from enhanced oxygen mobility at this interface; oxygen motion at the interface is further identified from 17O relaxometry experiments. The structure of this interface is solved by calculating the NMR parameters using density functional theory combined with random structure searching, allowing the chemistry underpinning the enhanced oxide-ion transport to be proposed. Finally, a comparison is made with 1% Gd-doped CeO2-SrTiO3 VAN films, for which greater NMR signal can be obtained due to paramagnetic relaxation enhancement, while the relative oxide-ion conductivities of the phases remain similar. These results highlight the information that can be obtained on interfacial structure and dynamics with solid-state NMR spectroscopy, in this and other nanostructured systems, our methodology being generally applicable to overcome sensitivity limitations in thin-film studies.