Standard high-temperature solid-state reactions of NaCl, Nb2O5, and SeO2 resulted in two new sodium selenites containing a second-order Jahn-Teller (SOJT) distorted Nb(5+) cation, namely, Na2Nb4O7(SeO3)4 (P1̅; 1) and NaNbO(SeO3)2 (Cmc21; 2). Compound 1 exhibits an unusual 3D [Nb4O7(SeO3)4](2-) anionic network composed of 2D [Nb4O11(SeO3)2](6-) layers which are further bridged by additional SeO3(2-) anions via corner sharing; the 2D [Nb4O11(SeO3)2](6-) layer is formed by unusual quadruple [Nb4O17](14-) niobium oxide chains of corner-sharing NbO6 octahedra being further interconnected by selenite anions via Nb-O-Se bridges. The polar compound 2 features a 1D [NbO(SeO3)2](-) anionic chain in which two neighboring Nb(5+) cations are bridged by one oxo and two selenite anions. The alignments of the polarizations from the NbO6 octahedra in 2 led to a strong SHG response of ∼7.8 × KDP (∼360 × α-SiO2), which is the largest among all phases found in metal-Nb(5+)-Se(4+)/metal-Nb(5+)-Te(4+)-O systems. Furthermore, the material is also type I phase matchable. The above experimental results are consistent with those based on DFT theoretical calculations. Thermal stabilities and optical properties for both compounds are also reported.