In this article, effects of annealing treatment on the evolution of microstructure, tensile properties and electrical resistivity of copper-graphene nanocomposites are investigated. In order to fabricate the nanocomposite, graphene nanopowder was ball-milled after being mixed with copper powder to form a mixture of copper-graphene powder (CuG). Hot rolled copper sheets were used as the matrix of the composite which were annealed prior to accumulative roll bonding (ARB). The nanocomposite was fabricated using 2, 4 and 6 cycles of ARB leading to 20, 40 and 160 multi-layered nanocomposites. Despite increased mechanical strength, the elongation to failure and the electrical conductivity were significantly reduced which were attributed to the high defect density after severe cold deformation and strength-ductility trade-off. The effect of cold deformation on increasing electrical resistivity was so significant that no positive effects of addition of 1% CuG on reducing resistivity was observed but a slight improvement was found in the sample with 2% CuG. However, after annealing at 500 C for 2 h, ductility was fully recovered to the initial value and the electrical resistivity was significantly reduced in the nanocomposite. This was attributed to the fact that a fully recrystallized grain structure was achieved after annealing. Percentage of reinforcing agent and the thickness of the stacking layers were found to determine the final grain size. Electrical conductivity of the nanocomposite was found to significantly improve with annealing. Indeed, the electrical conductivity of the annealed 6ARB-2%CuG composite was higher than the initially annealed copper sheet while the strength and ductility were increased, as well. This determines that the combination of ARB and annealing can be used as an effective method for fabrication of copper-graphene nanocomposites.