To exploit the combined strengthening effects of nanotwins and carbon nanotubes (CNTs) in Cu matrix composites, the nanotwins with a width ranging from 3 to 30 nm were incorporated into the CNTs-reinforced Cu matrix composites using cryogenic rolling and optimizing the initial particle size of the raw Cu powders. The formation of nanotwins in the Cu matrix composite reinforced by only 0.2 wt.% CNTs is accompanied by the increased dislocation density and refined Cu grain size, resulting in much better strength−ductility synergy than the referenced composite without significant nanotwins formation. The analysis of strengthening and toughening mechanisms demonstrates that the strength increment mainly derives from grain refinement strengthening, dislocation strengthening, and nanotwin strengthening. The strength increment from the contribution of the nanotwins accounts for 19.9% of the overall strength increment for the composite. Meanwhile, the retention of good tensile ductility can be reasonably explained by the increased dislocation accommodation ability due to the formed nanotwins and the decreased induced dislocation proliferation.