Mechanical metamaterials with three-dimensional micro- and nanoarchitectures exhibit unique mechanical properties, such as high specific modulus, specific strength, and energy absorption. However, a conflict exists between strength and recoverability in nearly all the mechanical metamaterials reported recently, in particular the architected micro/nanolattices, which restricts the applications of these materials in energy storage/absorption and mechanical actuation. Here, we demonstrated the fabrication of three-dimensional architected composite nanolattices that overcome the strength–recoverability trade-off. The nanolattices under study are made up of a high-entropy alloy-coated (14.2–126.1 nm in thickness) polymer strut (approximately 260 nm in the characteristic size) fabricated via two-photon lithography and magnetron sputtering deposition. In situ uniaxial compression inside a scanning electron microscope showed that these composite nanolattices exhibit a high specific strength of 0.027 MPa/kg m3, an ultrahigh energy absorption per unit volume of 4.0 MJ/m3, and nearly complete recovery after compression under strains exceeding 50%, thus overcoming the traditional strength–recoverability trade-off. During multiple compression cycles, the composite nanolattices exhibit a high energy loss coefficient (converged value after multiple cycles) of 0.5–0.6 at a compressive strain beyond 50%, surpassing the coefficients of all the micro/nanolattices fabricated recently. Our experiments also revealed that, for a given unit cell size, the composite nanolattices coated with a high entropy alloy with thickness in the range of 14–50 nm have the optimal specific modulus, specific strength, and energy absorption per unit volume, which is related to a transition of the dominant deformation mechanism from local buckling to brittle fracture of the struts.