For the fabrication of high-strength carbon nanotube (CNT) reinforced Al matrix composites, the uniform dispersion, strong interface bonding and high structural integrity of CNTs have been regarded as the three most important issues. In this work, two distinct approaches, namely high shear dispersion (HSD) and shift-speed ball milling (SSBM), were applied to disperse CNTs (1.5 wt%) into pure Al powders. These two kinds of CNT/Al composite powders as well as the pure Al powder (as a comparison) were deposited onto stainless steel plates by cold spraying using different processing parameters. The velocity and the temperature of the particle prior to impact was simulated by the commercial code of Fluent. The deposition efficiency, microstructure evolution, as well as the distribution and structural integrity of CNTs in the composite coatings produced from different starting powders were comparatively investigated in terms of X-ray diffraction (XRD), Raman spectra, and electron back scanning diffraction (EBSD). According to the XRD and Raman analysis, no new phases such as oxides or brittle Al4C3 were detectable in both CNT/Al composite coatings. Some structural damages of CNTs were found in both composite coatings, especially the one fabricated from HSD composite powder. The dispersion of CNTs onto Al particle surfaces by HSD approach did not achieve a significant strengthening effect on the composite coatings, but adversely affected the metallic bonding of the particles and the substrate. The microhardness of the CNT/Al composite coating produced from SSBM powders reached around ~115 HV0.1, showing a significant improvement compared to the pure Al coating mainly due to the grain refinement and CNTs strengthening.