This work uses high-pressure torsion (HPT) to fabricate nanostructured graphite-reinforced Inconel 718 metal matrix composites. The initial powders were pretreated by a colloidal mixing (CM) step to mitigate graphite particle agglomeration and improve the powder blend homogeneity. Scanning electron microscopy investigations show the formation of a nanocrystalline solid solution of the Inconel 718 matrix. Comprehensive statistical image analysis is used to study graphite evolution after deformation in dependency of concentrations and processing routes. It is shown that CM improves composite processability, significantly reducing graphite agglomerate size (80 pct), and improving graphite distribution homogeneity. Raman spectroscopy measurements reveal the structural state of graphite, showing a minimal effect of CM on graphite defect density, while HPT induces a significant increase. Despite the structural degradation, no amorphization is observed, and crystalline domain sizes remain constant in the nanocrystalline range, independent of the applied shear strain. The nanoindentation hardness tested at room temperature is higher for graphite-reinforced composites compared to the Inconel 718 reference alloy. High-temperature in situ nanoindentation tests reveal that the indentation hardness of the CM-processed composite measured at 823 K even surpasses the hardness of the pure reference alloy at room temperature.