This work proposes a facile and new approach that uses graft copolymerization and amidation reaction to prepare shape memory polymer (SMP) based on natural rubber (NR). The poly(methyl methacrylate) modified NR (MGNR) is cross-linked with diamine through an amidation reaction. In this kind of approach, a novel type of cross-linked MGNR with a three-dimensional network of amide linkage was prepared. The solvent resistance, mechanical properties, and phase morphology of MGNRs were significantly improved after being cross-linked by a diamine cross-linker. Additionally, the cross-linked MGNR40 also exhibited excellent shape fixation and shape recovery. This is a direct result of the vitrification of the grafted PMMA domains at low temperatures, preventing elastic recovery. Meanwhile, a cross-linked network from amide linkage facilitates recovery force upon heating. Hence, the shape memory performance of MGNRs can be tuned with both grafted PMMA content and the degree of diamine cross-link. The strategy in this research work offered an effective and convenient method to obtain cross-linked MGNR with unique molecular architecture. Consequently, this cross-linked MGNR delivered excellent mechanical strength and shape memory performance.