Alloy and microstructure optimization have led to impressive improvements in the strength of engineering metals, while the range of Young’s moduli achievable has remained essentially unchanged. This is because stiffness is insensitive to microstructure and bounded by individual components in composites. Here we design ultra-low stiffness in fully dense, nanostructured metals via the stabilization of a mechanically unstable, negative stiffness state of a martensitic alloy by its coherent integration with a compatible, stable second component. Explicit large-scale molecular dynamics simulations of the metamaterials with state of the art potentials confirm the expected ultra-low stiffness while maintaining full strength. We find moduli as low as 2 GPa, a value typical of soft materials and over one order of magnitude lower than either constituent, defying long-standing composite bounds. Such properties are attractive for flexible electronics and implantable devices. Our concept is generally applicable and could significantly enhance materials science design space.