Highly flexible, conductive, and shape memory polyurethane nanocomposites were prepared using a robust and fast process. Functionalized graphene sheets were incorporated as crosslinkers in the prepolymer, prepared from a reaction of 4,4′-methylene bis(phenyl isocyanate) and poly(ε-caprolactone)diol. The covalently bonded graphene sheets were homogeneously dispersed in the polymer matrix. In comparison to pristine polyurethane and carbon nanotube-crosslinked polyurethane, the graphene-crosslinked polyurethane composite exhibited higher modulus and breaking stress, and exceptional elongation-at-break. The resulting composite exhibited 97% shape recovery, 95% shape retention, enhanced shape recovery force, and fast electroactive shape recovery rate, thus it could be a promising material for the fabrication of graphene-based actuating devices.