We report a new noncentrosymmetric barium tellurium borate, Ba4B8TeO19 that has potential ultraviolet (UV) nonlinear optical (NLO) applications. Ba4B8TeO19 was synthesized by a flux method and crystallizes in the noncentrosymmetric space group Cc. The material exhibits a framework structure of [B8O17]∞ double layers connected to distorted TeO6 octahedra. Second harmonic generation (SHG) measurements at 1064 and 532 nm on polycrystalline Ba4B8TeO19 indicate that the title compound is phase-matchable (type I) with a moderate SHG response (1 × KH2PO4 at 1064 nm and 0.2 × β-BaB2O4 at 532 nm). In addition, a short absorption edge (210 nm) was measured. Using density functional theory calculations, we show that the SHG response originates from contributions from O 2p and Te 5s states at the valence and conduction band edges. Finally, by computing the linear optical properties, we find that this compound displays a moderate birefringence of 0.055 at 1064 nm and 0.059 at 532 nm, necessary conditions for phase-matching in UV NLO materials.