Two-dimensional materials have become of great importance and are widely studied both in terms of new physics as well as for device applications. Although much is known about the properties of many bulk two-dimensional materials, much less is known about the properties due to grain boundaries or at interfaces of two-dimensional materials. A better theoretical understanding of the properties of grain boundaries in polycrystalline two-dimensional materials and the properties of heterostructures of two-dimensional materials however crucially relies on first finding their atomic structure. We apply the ab initio random structure searching (AIRSS) approach, previously primarily applied to bulk structure prediction, to structure prediction of interfaces in two-dimensional materials. The method can be applied to both grain boundary structures as well as investigating heterostructure interfaces. It is based on density functional theory, in combination with high-throughput computing. Many possible materials can be studied (for instance, graphene, h-BN, phosphorene).