Aluminum and its alloy are of importance due to high specific strength. In particular, aluminum matrix composites have good corrosion resistance and mechanical property at high temperatures. However, enhanced mechanical strength and wear resistance via proper heat treatments are strongly required for many structural applications. For this purpose, we synthesized carbon nanotube (CNT)-reinforced aluminum matrix composites by employing a new method. We employed controlled ball-milling and sintering: the use of some specific process control agents (PCAs) for ball-milling and sintering in a specific atmosphere. The use of our PCAs was beneficial both for homogeneous mixing and for the formation of hard dispersoids. Hardened layers was formed at the surface of the present aluminum-CNT composites as a result of reaction of aluminum with PCAs and nitrogen in the processing atmosphere. The resulting materials after sintering showed interesting mechanical properties, combined with surface hardening. The hardening mainly stems from the formation of Al-N-O phase at the surface of specimens.