Carbon nanotube (CNT) reinforced aluminum (Al) matrix composite materials were successfully fabricated by mechanical ball milling followed by powder hot extrusion processes. Microstructural analysis revealed that the CNTs were well dispersed at the boundaries and were aligned with the extrusion direction in the composites obtained. Although only a small quantity of CNTs were added to the composite (1 vol%), the Vickers hardness and the tensile strength were significantly enhanced, with an up to three-fold increase relative to that of pure Al. From the fractography of the extruded Al-CNT composite, several shapes were observed in the fracture surface, and this unique morphology is discussed based on the strengthening mechanism. The damage in the CNTs was investigated with Raman spectroscopy. However, the Al-CNT composite materials were not only strengthened by the addition of CNTs but also enhanced by several synergistic effects. The nanoindentation stress-strain curve was successfully constructed by setting the effective zero-load and zero-displacement points and was compared with the tensile stress-strain curve. The yield strengths of the Al-CNT composites from the nanoindentation and tensile tests were compared and discussed. We believe that the yield strength can be predicted using a simple nanoindentation stress/strain curve and that this method will be useful for materials that are difficult to machine, such as complex ceramics.