A double-network polymer hydrogel composed of chemically cross-linked poly(ethylene glycol) (PEG) and physically cross-linked poly(vinyl alcohol) (PVA) was prepared. When the hydrogel (70 wt % of water) is subjected to freezing/thawing treatment under strain, the enhanced physical network as a result of crystallization of PVA chains can stabilize the hydrogel deformation after removal of the external force at room temperature. Subsequent disruption of the physical network of PVA by heating allows for the recovery of the initial shape of the hydrogel. Moreover, the double-network hydrogel exhibits self-healing capability stemming from the physical network of PVA by virtue of the extensive interchain hydrogen bonding between the hydroxyl side groups. This study thus demonstrates a general approach to imparting both the shape memory and self-healing properties to chemically cross-linked hydrogels that otherwise do not have such functionalities. Moreover, by making use of the fixed hydrogel elongation, the effect of anisotropy arising from chain orientation on the self-healing was also observed.