Experiments have demonstrated the successful fabrication of composites of multi-wall carbon nanotubes (CNT) with both 304 and 316 stainless steel (SS) using ball milling and spark plasma sintering (SPS). The retention of CNT structures after the SPS process was confirmed by x-ray diffraction, Raman spectroscopy and field emission scanning electron microscopy. At a concentration between 0.5-2.0 wt.%, CNT increased the Vickers hardness and compressive yield strength of 304 SS and 316 SS significantly. These results show that composites of CNT and SS are harder and stronger materials than pristine steels. Potential oilfield and offshore applications can be many depending on whether the CNT-SS composites are fabricated as pellets, coatings or wires.