Use of liquefied natural gas (LNG) as energy source has received much interest in multiple industries. Its world-wide storage market is projected to increase significantly over the coming years. The most widely used material for building storage infrastructure is the 9% nickel steel, which is expensive as a result of high nickel (content) and cumbersome production process. High manganese (Mn) steels possess attractive attributes to mitigate this challenge of high cost. Moreover, Mn is equally an austenite phase stabilizer and affordable than Ni. Despite appealing properties, binary face centered cubic (FCC) Fe-Mn alloys containing higher Mn content suffers from low yield strength. Consequently, current study employs density functional theory (DFT) based first-principles calculations to investigate the effect of Al, Ni, and Cr additions on structural and elastic properties of FCC Fe75Mn25 alloys. Al addition is found to increase lattice constant and enhance thermodynamic stability the most, while Cr improves elastic modulus and ductility, suggesting it as the most promising alloying element for LNG storage applications.