The new compound NaCu4Se4 forms by the reaction of CuO and Cu in a molten sodium polyselenide flux, with the existence of CuO being unexpectedly critical to its synthesis. It adopts a layered hexagonal structure (space group P6(3)/mmc with cell parameters a = 3.9931(6) angstrom and c = 25.167(5) angstrom), consisting of infinite two-dimensional [Cu4Se4]-slabs separated by Na+ cations. X-ray photoelectron spectroscopy suggests that NaCu4Se4 is mixed-valent with the formula (Na+)-(Cu+)(4)(Se2-)(Se-)(Se-2)(2-). NaCu4Se4 is a p-type metal with a carrier density of similar to 10(21) cm(-3) and a high hole mobility of similar to 808 cm(2) s(-1) at 2 K based on electronic transport measurements. First-principles calculations suggest the density of states around the Fermi level are composed of Cu-d and Se-p orbitals. At 2 K, a very large transverse magnetoresistance of similar to 1400% was observed, with a nonsaturating, linear dependence on field up to 9 T. Our results indicate that the use of metal oxide chemical precursors can open reaction paths to new low-dimensional compounds.