Carbon fiber–reinforced epoxy resin composites (CF/EP) modified with nitrile rubber (NBR) and multi-walled carbon nanotube (CNT) were prepared, and their shape memory behavior and physical mechanical properties were studied. NBR/CF/EP composite showed a relative lower bending strength than pure CF/EP composite, and a remarkable increase of bending strength was achieved for CNT/CF/EP composite. The bending strength of all samples increased after postcure process. All samples showed a similar glass transition temperature, but CNT/CF/EP composite could recover at lower temperature and faster speed, while NBR/CF/EP composite was just the opposite. During folding-recovery cycles, internal damage increased with folding times, which led to a general decrease in bending strength, storage modulus, and shape recovery ratio. The anomaly of slight increase in bending strength resulted from the further curing at high temperature during the folding-recovery cycles. Among the three kinds of samples, NBR/CF/EP composite showed the best folding-recovery precision, recovery repeatability, and recovery capability of bending strength, which was considered resulting from the various damage mechanisms. Compared with the cracks in the CNT/CF/EP composite, the rubber deformation and plastic deformation of the matrix of NBR/CF/EP composite prior to the occurrence of cracks were easier to recover during the inadvertent or intentional postcure process.