Multi-scale “rigid-soft” material coating has been an effective strategy for enhancing the interfacial shear strength (IFSS) of carbon fibers (CFs), which is one of the key themes in composite research. In this study, a soft material, chitosan (CS), and a rigid material, carbon nanotubes (CNTs), were sequentially grafted onto the CFs surface by a two-step amination reaction. The construction of the “rigid-soft” structure significantly increased the roughness and activity of the CFs surface, which improved the mechanical interlocking and chemical bonding between the CFs and resin. The interfacial shear strength (IFSS) of the CS- and CNT-modified CFs composites increased by 186.9% to 123.65 MPa compared to the desized fibers. In addition, the tensile strength of the modified CFs was also enhanced by 26.79% after coating with CS and CNTs. This strategy of establishing a “rigid-soft” gradient modulus interfacial layer with simple and non-destructive operation provides a valuable reference for obtaining high-performance CFs composites.