Three-dimensional higher-order eXtended finite element method (XFEM) - computations still pose challenging computational geometry problems especially for moving interfaces. This paper provides a method for the localization of a higher-order interface finite element (FE) mesh in an underlying three-dimensional higher-order FE mesh. Additionally, it demonstrates, how a subtetrahedralization of an intersected element can be obtained, which preserves the possibly curved interface and allows therefore exact numerical integration. The proposed interface algorithm collects initially a set of possibly intersecting elements by comparing their ?eXtended axis-aligned bounding boxes?. The intersection method is applied to a highly reduced number of intersection candidates. The resulting linearized interface is used as input for an elementwise constrained Delaunay tetrahedralization, which computes an appropriate subdivision for each intersected element. The curved interface is recovered from the linearized interface in the last step. The output comprises triangular integration cells representing the interface and tetrahedral integration cells for each intersected element. Application of the interface algorithm currently concentrates on fluid-structure interaction problems on low-order and higher-order FE meshes, which may be composed of any arbitrary element types such as hexahedra, tetrahedra, wedges, etc. Nevertheless, other XFEM-problems with explicitly given interfaces or discontinuities may be tackled in addition. Multiple structures and interfaces per intersected element can be handled without any additional difficulties. Several parallelization strategies exist depending on the desired domain decomposition approach. Numerical test cases including various geometrical exceptions demonstrate the accuracy, robustness and efficiency of the interface handling.