A new ternary selenide, Na2Mn3Se4, was prepared by a stoichiometric reaction between Na2Se4 and metallic Mn at 923 K Crystal structure determination revealed a new structure type, built of alternating layers of Na+ ions and [Mn3Se4](2-) anionic slabs. Band structure calculations indicate that Na2Mn3Se4 is an indirect band gap semiconductor with E-g = 1.59 eV, although a direct band gap is only marginally larger, at 1.64 eV. The material shows antiferromagnetic (AFM) ordering at 27 K, while the Weiss constant of similar to-400 K suggests much stronger nearest-neighbor AFM exchange between the Mn sites. This discrepancy is attributed to the strong spin frustration caused by a triangulated arrangement of the Mn sites in the [Mn3Se4](2-) layer. The magnetic frustration leads to the stabilization of a complex AFM ordered structure with non-collinear arrangement of the Mn magnetic moments, as established from neutron diffraction data.