Nanocrystalline metals--with grain sizes of less than 100 nm--have strengths exceeding those of coarse-grained and even alloyed metals, and are thus expected to have many applications. For example, pure nanocrystalline Cu (refs 1-7) has a yield strength in excess of 400 MPa, which is six times higher than that of coarse-grained Cu. But nanocrystalline materials often exhibit low tensile ductility at room temperature, which limits their practical utility. The elongation to failure is typically less than a few per cent; the regime of uniform deformation is even smaller. Here we describe a thermomechanical treatment of Cu that results in a bimodal grain size distribution, with micrometre-sized grains embedded inside a matrix of nanocrystalline and ultrafine (<300 nm) grains. The matrix grains impart high strength, as expected from an extrapolation of the Hall-Petch relationship. Meanwhile, the inhomogeneous microstructure induces strain hardening mechanisms that stabilize the tensile deformation, leading to a high tensile ductility--65% elongation to failure, and 30% uniform elongation. We expect that these results will have implications in the development of tough nanostructured metals for forming operations and high-performance structural applications including microelectromechanical and biomedical systems.