Carbon nanotube reinforced nickel matrix composites (Ni/CNT) with different CNT compositions were fabricated by solid state processing and subjected to severe plastic deformation (SPD) by means of high pressure torsion (HPT). A thorough study on the microstructural changes during heating and on the thermal stability was performed using differential scanning calorimetry (DSC), high temperature X-ray diffraction (HT-XRD) and electron backscattered diffraction (EBSD). Furthermore, the formation and dissolution of the metastable nickel carbide Ni₃C phase was evidenced by DSC and HT-XRD in composites, where sufficient carbon atoms are available, as a consequence of irreversible damage on the CNT introduced by HPT. Finally, it was shown that the composites exhibited an improved thermal stability with respect to nickel samples processed under the same conditions, with a final grain size dependent on the CNT volume fraction according to a V_CNT^−1/3 relationship and that lied within the ultrafine grained range.