We have studied the lattice stability of face centred cubic (fcc) versus hexagonal close packed (hcp) Fe-Mn random alloys using ab initio calculations. In the calculations we considered the antiferromagnetic order of local moments, which for fcc alloys models the magnetic configuration of this phase at room temperature (below its Néel temperature) as well as their complete disorder, corresponding to paramagnetic fcc and hcp alloys. For both cases, the results are consistent with our thermodynamic calculations, obtained within the Calphad approach. For the room temperature magnetic configuration, the cross-over of the total energies of the hcp phase and the fcc phase of Fe-Mn alloys is at the expected Mn content, whereas for the magnetic configuration above the fcc Néel temperature, the hcp lattice is more stable within the whole composition range studied. The increase of the total energy difference between hcp and antiferromagnetic fcc due to additions of Mn as well as the stabilizing effect of antiferromagnetic ordering on the fcc phase are well displayed. These results are of relevance for understanding the deformation mechanisms of these random alloys.