Bulk nanostructured metals can attribute both exceptional strength and poor thermal stability to high interfacial content, making it a challenge to utilize them in high-temperature environments. Here we report that a bulk two-phase bimetal nanocomposite synthesised via severe plastic deformation uniquely possesses simultaneous high-strength and high thermal stability. For a bimetal spacing of 10 nm, this composite achieves an order of magnitude increase in hardness of 4.13 GPa over its constituents and maintains it (4.07 GPa), even after annealing at 500 °C for 1 h. It owes this extraordinary property to an atomically well-ordered bimaterial interface that results from twin-induced crystal reorientation, persists after extreme strains and prevails over the entire bulk. This discovery proves that interfaces can be designed within bulk nanostructured composites to radically outperform previously prepared bulk nanocrystalline materials, with respect to both mechanical and thermal stability.