A novel water-induced shape memory polymer based on polyvinyl alcohol (PVA) was prepared by introducing graphene oxide (GO). Due to the strong hydrogen bonding interaction between PVA and GO, some additional physically cross-linked points could be formed in PVA, which largely improved shape memory properties of PVA. Solvent-induced shape memory behavior was observed by immersing PVA/GO nanocomposites in water. The water-induced shape recovery was due to the decrease of glass transition temperature and storage modulus. This could be explained by the swelling plasticizing effect of water on PVA, as indicated by the obvious expansion in volume of PVA. On the other hand, the weakened hydrogen bonding between PVA and GO was also observed after immersing the PVA/GO nanocomposites in water. Thus both the plasticizing effect and the competitive hydrogen bonding were the two main reasons for the shape recovery of PVA/GO nanocomposites. This study provides a framework for developing new shape memory polymers (SMPs) and for better understanding the shape recovery mechanism in solvent-induced SMPs.