The interface and interfacial reactions in Al-matrix composites reinforced with multi-walled carbon nanotubes (MWCNTs) were thoroughly investigated by high-resolution transmission electron microscopy combined with a precisely controlled heat treatment in the solid state. It was shown that MWCNT (002) formed a coherent interface with the low-index Al planes of Al (111), Al (220), and Al (002), realizing a stable interface. Aluminum carbides (Al4C3) were preferentially formed at the active prism plane edges sited at the open ends and acid treatment-induced surface nanodefects of MWCNTs. The Al4C3 maintained the shape of the pristine MWCNT and showed a typical orientation relationship with the Al matrix, that is, Al (111)//Al4C3 (001). It was suggested that the diffusion of Al atoms through Al4C3 dominated the growth of Al4C3; the Al4C3 originated at the open MWCNT tips may quickly grow in the <100> direction of the MWCNT, while the nanodefect-originated Al4C3 may grow simultaneously in the <110> and <100> directions of the MWCNT. The activation energy of Al4C3 formation, the appearance of twinning in single-crystal Al4C3, and the possible influence of the Al4C3 formation on the enhancement of load transfer at the MWCNT/Al interface were also studied.