Single-walled carbon nanotubes (SWCNTs) have excellent intrinsic mechanical properties and would not suffer from inter-layer sliding as their multi-walled counterparts, making them promising reinforcing candidates for advanced metal matrix composites. In this study, we fabricated nanolaminated SWCNT-aluminum (Al) composites where the SWCNTs were uniformly distributed at the lamella boundaries and were tightly bonded with the Al matrix. Macroscopic tensile tests showed a considerable strengthening effect as a result of SWCNT inclusion, while the uniform elongation of the composites remained unchanged as compared to unreinforced Al. Subsequent micro-pillar compression tests at various pillar orientations and strain rates, together with associated post-mortem site-specific microstructural analysis, revealed that this SWCNT-induced strengthening in the composites can be rationalized by a combined effect from the grain refinement in the Al matrix, the load-sharing of the CNTs, and their alteration of the intrinsic deformation mechanism of the Al matrix.