A new shape memory polymer (SMP) was prepared from an ABA triblock copolymer with polystyrene (PS) end blocks and a random copolymer midblock of poly(methylacrylate-random-octadecylacrylate) (PMA-r-PODA). The self-assembly of the triblock copolymer generates a three-dimensional, physically cross-linked network by the bridging of the midblocks across the glassy PS domains, which is used as the permanent network in the SMP. A second reversible network is generated by the side-chain crystallization of the PODA side-chains. Shape memory testing by uniaxial deformation and recovery of molded tensile bars demonstrated that shape fixities greater than 96% and shape recoveries greater than 98% were obtained for extensional strains up to 300%. Although some loss of properties was observed with cycling, the entirely physically cross-linked nature of the polymer allowed erasing of the sample history and recovery of the initial properties by annealing the sample at elevated temperature.