Nanocrystalline metals, with a mean grain size of less than 100 nanometres, have greater room-temperature strength than their coarse-grained equivalents, in part owing to a large reduction in grain size1. However, this high strength generally comes with substantial losses in other mechanical properties, such as creep resistance, which limits their practical utility; for example, creep rates in nanocrystalline copper are about four orders of magnitude higher than those in typical coarse-grained copper2,3. The degradation of creep resistance in nanocrystalline materials is in part due to an increase in the volume fraction of grain boundaries, which lack long-range crystalline order and lead to processes such as diffusional creep, sliding and rotation3. Here we show that nanocrystalline copper-tantalum alloys possess an unprecedented combination of properties: high strength combined with extremely high-temperature creep resistance, while maintaining mechanical and thermal stability. Precursory work on this family of immiscible alloys has previously highlighted their thermo-mechanical stability and strength4,5, which has motivated their study under more extreme conditions, such as creep. We find a steady-state creep rate of less than 10−6 per second—six to eight orders of magnitude lower than most nanocrystalline metals—at various temperatures between 0.5 and 0.64 times the melting temperature of the matrix (1,356 kelvin) under an applied stress ranging from 0.85 per cent to 1.2 per cent of the shear modulus. The unusual combination of properties in our nanocrystalline alloy is achieved via a processing route that creates distinct nanoclusters of atoms that pin grain boundaries within the alloy. This pinning improves the kinetic stability of the grains by increasing the energy barrier for grain-boundary sliding and rotation and by inhibiting grain coarsening, under extremely long-term creep conditions. Our processing approach should enable the development of microstructurally stable structural alloys with high strength and creep resistance for various high-temperature applications, including in the aerospace, naval, civilian infrastructure and energy sectors.