Shape-memory polymers can revert to their original shape when they are reheated. The stress generated by shape recovery is a growing function of the energy absorbed during deformation at a high temperature; thus, high energy to failure is a necessary condition for strong shape-memory materials. We report on the properties of composite nanotube fibers that exhibit this particular feature. We observed that these composites can generate a stress upon shape recovery up to two orders of magnitude greater than that generated by conventional polymers. In addition, the nanoparticles induce a broadening of the glass transition and a temperature memory with a peak of recovery stress at the temperature of their initial deformation.