Magnetocrystalline anisotropy (MCA) of Fe(001) interfaces with various non-magnetic metals (Hf, Zr, Ti, Ta, Nb, V, Ir, Rh, Pt, Pd, Au, Ag, Cu, and Zn) was investigated by first-principles calculations. We found that Fe interfaces with non-magnetic metals with fully occupied d states tend to show perpendicular MCA. The spin-orbit coupling in interfacial Fe atoms plays an important role in perpendicular MCA. Conversely, Fe interfaces with non-magnetic metals with partially occupied d states exhibit in-plane MCA. The Hf/Fe(001) interface shows an exceptionally large perpendicular MCA energy of 1.5 mJ/m2, which corresponds to that of the MgO/Fe(001) interface. In these cases, contributions from interfacial Fe atoms to MCA are relatively small, and the large spin-orbit coupling of non-magnetic atoms is the primary contribution to MCA. We conclude that formation of Hf/Fe(001) interfaces will enhance the perpendicular magnetization of MgO/CoFeB-based magnetic tunnel junctions.