Two new vanadium tellurites, VTeO4(OH) (1) and Ba2V4O8(Te3O10) (2), have been synthesized successfully with the use of hydrothermal reactions. The crystal structures of the two compounds were determined by single-crystal X-ray diffraction. Compound 1 crystallizes in the polar space group Pca21 (No. 29) while compound 2 crystallizes in the centrosymmetric space group C2/c (No. 15). The topography of compound 1 reveals a two-dimensional, layered structure comprised of VO6 octahedral chains and TeO3(OH) zig-zag chains. Compound 2, on the contrary, features a three-dimensional [V4O8(Te3O10)]4- anionic framework with Ba2+ ions filled into the 10-member ring helical tunnels. The [V4O8(Te3O10)]4- anionic network is the first 3D vanadium tellurite framework to be discovered in the alkaline-earth vanadium tellurite system. Powder second harmonic generation (SHG) measurements indicate that compound 1 shows a weak SHG response of about 0.3×KDP (KH2PO4) under 1064nm laser radiation. Infrared spectroscopy, elemental analysis, thermal analysis, and dipole moment calculations have also been carried out.