Interfacial perpendicular magnetic anisotropy in the Fe/MgO heterostructure has attracted increasing attention because of its potential usage in building out-of-plane magnetized magnetic tunnel junctions for spin-transfer-torque magnetic random-access memory devices. A large interfacial anisotropy constant (Ki) is required to achieve a high thermal stability that is critical for large-capacity magnetic tunnel junctions. Here, we show that inserting one layer of appropriate heavy elements (X) at the interface of Fe/MgO can significantly enhance Ki using first-principles electronic structure calculations. A total number of 33 X metal elements including 3d, 4d, and 5d transition metals and 4p, 5p, and 6p main group elements were considered. By analyzing the interfacial magnetic anisotropy and interfacial bonding strength of Fe/X/MgO, we are able to identify three promising heavy transition-metal elements including W, Re, and Pt for enhancing perpendicular magnetic anisotropy in Fe/MgO, with an improved Ki of 2.43, 2.37, and 9.74 mJ/m2, respectively. This work indicates that interfacial engineering is one effective way to modify the interfacial magnetic anisotropic property.