This paper presents data on fabrication of "nickel-graphene-graphite" bulk composites using powder metallurgy methods combined with the high energy ball milling. The composites were then processed by high pressure torsion (HPT) at temperatures of 23 and 200°C. This treatment gives rise to the formation of new "nanostructured nickel-graphene" composites. The phase composition of the new composite specimens was examined by X-ray diffraction. Raman spectroscopy proved graphite-to-graphene conversion under mechanical treatments. The microstructure of the new composite specimens was investigated by scanning electron and transmission electron microscopy methods. Composite specimens after HPT at temperature of 200°C demonstrate the optimal combination of strength (σ₀₂= 923 MPa; σ_b= 992 MPa) and ductility (δ = 99%). Composite specimens with 2 wt.% graphene content after HPT at room temperature exhibits superior microhardness H_v = 6.45 GPa.