In this study, a novel multi-walled carbon nanotubes reinforced nanocrystalline copper matrix composite with super high strength and moderate plasticity was synthesized. We successfully overcome the agglomeration problem of the carbon nanotubes and the grain growth problem of the nanocrystalline copper matrix by combined use of the electroless deposition and spark plasma sintering methods. The yield strength of the composite reach up to 692 MPa, which is increased by 2 and 5 times comparing with those of the nanocrystalline and coarse copper, respectively. Simultaneously, the plasticity of the composite was also significantly increased in contrast with that of the nanocrystalline copper. The increase of the density of the carbon nanotubes after coating, the isolation effect caused by the copper coating, and the improvement of the compatibility between the reinforcements and matrix as well as the effective control of the grain growth of the copper matrix all contribute to improving the mechanical properties of the composite. In addition, a new strengthening mechanism, i.e., the series-connection effect of the nanocrystalline copper grains introduced by carbon nanotubes, is proposed to further explain the mechanical behavior of the nanocomposite.