Interfaces and grain boundaries are of great importance for the physical properties of many materials. It is however often very difficult to experimentally determine the theoretical crystal structure of interfaces. This inherently limits (or altogether prevents) how much knowledge can be gained from computational and theoretical approaches such as density functional theory. We have developed an approach based on the ab initio random structure searching (AIRSS) method to predict the crystal structure of interfaces in three-dimensional materials. The approach is based on density functional theory in combination with a high-throughput structure prediction approach. In close collaboration with experimental research groups both in Cambridge and Japan, oxides interfaces will be selected for which the detailed atomistic structure is undetermined. Using AIRSS, and experimental constraints, we will resolve the structure.