The shape memory behavior of a series of strong, tough hybrid hydrogels prepared by covalently cross-linking quad-polymers of N,N-dimethylacrylamide (DMA), 2-(N-ethylperfluoro-octanesulfonamido) ethyl methacrylate (FOSM), hydroxyethyl acrylate, and 2-cinnamoyloxyethyl acrylate was investigated. The hybrid hydrogels, which had physical and covalent cross-links, contained ∼60–70% water, were relatively soft and elastic, and exhibited high mechanical strength, extensibility, and fracture toughness. The temporary network was derived from glassy nanodomains due to microphase separation of the FOSM species. The switching temperature for shape memory was the glass transition temperature of the nanodomains. Some creep relaxation occurred in the fixed shape due to viscoelastic effects of the nanodomain cross-links, but shape fixing efficiencies of 84–88% were achieved for the fixed shape after 24 h at 10 °C. Shape recovery to the permanent shape was achieved by reheating the hydrogel to 65 °C and was essentially quantitative.