Introducing carbon nanotubes (CNTs) to form a multiscale reinforcing structure is regarded as an unique approach to effectively improve the interface property of metal matrix composites. Curved CNTs were grafted onto the surface of the carbon fiber fabrics by injection chemical vapor deposition, and pieces of fabrics were further stitched into preform. Carbon fiber grafted with CNTs-reinforced magnesium matrix composites (CNTs-C-f/Mg) was prepared by squeeze casting. The influence of grafted CNTs on the interfacial microstructure and mechanical properties was investigated. The results showed that the carbon fiber preform grafted with CNTs was fully infiltrated with the melt matrix alloy. The larger Al8Mn5-phase particles were refined by grafted CNTs, and a transition layer of Al8Mn5/CNTs was formed on the surface of carbon fiber. Tensile strength and bending strength of the CNTs-C-f/Mg composite were significantly increased compared to the composite without grafted CNTs by 33% and 29%, respectively. The fracture morphologies confirmed that the enhanced plasticity of matrix alloy near the interface prevented obvious debonding after grafting CNTs on carbon fiber. The main operative mechanism by CNTs was attributed to optimized interface fracture behavior. This could be a very prominent method to adjust the interface structure and improve the properties of composites.