$Na^+$ ion conductivity can be improved by the substitution of an Mg atom for an Al atom to form a nonstoichiometric $Na^+$ $eta$-alumina. We performed a first principles study to investigate the most stable substitution site of an Mg atom and the resulting structural change of the nonstoichiometric $Na^+$ $eta$-alumina. Al atoms were classified as four different layers in the spinel block that are separated by conduction planes in the nonstoichiometric $Na^+$ $eta$-alumina. The substitution of an Mg atom for an Al atom at a tetragonal site was more favorable than that at an octahedral site. The substitution in the spinel block was more favorable than that close to the conduction plane. This result was well explained by the volume changes of the polyhedrons, by the standard deviation of the Mg-O distance, and by the comparison with bulk MgO structure. Our result indicates that the most preferable site for the Mg atom was the tetrahedral site at the spinel block in the nonstoichiometric $Na^+$ $eta$-alumina.