A new structure located in the TiO2-rich corner of the BaO-Ce2O3-TiO2 system crystallizes with an orthorhombic unit cell, space group Pnma, and with lattice parameters a = 27.88(1), b = 7.745(2), and c = 17.350(4) Angstrom. Refinement on F resulted in R1 = 6.46% for 3868 F-0 > 4 sigma. The structure is made up of a network of corner-sharing TiO6 octahedra creating rhombic (perovskite-like) and pentagonal channels. In this new structure, there are eight unique rhombic positions (occupied chiefly by Ce atoms), four unique pentagonal positions (occupied chiefly by Ba atoms), and eight unique Ti positions. Full occupation of the sites would correspond to the formula Ba16Ce32Ti64O192; however, refinement of the site occupancies of the Ce and Ba atoms suggests some substitution of the cations and vacancies. Electron probe wavelength dispersive spectroscopic microanalysis averaged from twenty measurements on three crystals＇ results in 4.68 +/- 0.11 at% Ba, 9.63 +/- 0.30 at% Ce, and 18.57 +/- 0.35 at% Ti.