Double-pass Friction Stir Processing (FSP) was applied to fabricate an AZ31/CNT nano-composite for surface hardening of lightweight structural components. The effects of double-pass FSP as well as groove depth (i.e., volume fraction of CNT) on the CNT distribution, dynamically recrystallized grain size, and resulting microhardness were studied. Double-pass FSP was performed for the CNT-filled plate-type specimen with different groove depths of 2, 3, and 4 mm. By applying double-pass FSP, the average size of CNT clusters decreased, implying a more homogeneous distribution. Compared with the FSPed specimen without CNT, grain size was refined from 19 μm to 3 μm and microhardness increased from 52 Hv to 83 Hv (i.e., 71% increase).