The magnetic and crystal structures of the alpha-NaMnO2 have been determined by high-resolution neutron powder diffraction. The system maps out a frustrated triangular spin lattice with anisotropic interactions that displays two-dimensional spin correlations below 200 K. Magnetic frustration is lifted through magneto-elastic coupling, evidenced by strong anisotropic broadening of the diffraction profiles at high temperature and ultimately by a structural phase transition at 45 K. In this low-temperature regime a three-dimensional antiferromagnetic state is observed with a propagation vector k=(1/2,1/2,0).