A new layered Ti-based pnictide oxide superconductor, Ba1-xNaxTi2Sb2O (0.0 <= x <= 0.33), is reported. X-ray studies revealed that it crystallizes in the tetragonal CeCr2Si2C structure. The undoped parent compound, BaTi2Sb2O [P4/mmm; a = 4.1196(1) angstrom; c = 8.0951(2) angstrom], exhibits a charge density wave (CDW)/spin density wave (SDW) transition at 54 K. Upon chemical doping with Na, the CDW/SDW transition is systematically suppressed, and superconductivity arises with the critical temperature (T-c) increasing to 5.5 K. Bulk superconductivity was confirmed by resistivity, magnetic, and heat capacity measurements. Like the high-T-c cuprates and the iron pnictides, the superconductivity in BaTi2Sb2O arises from an ordered state. Similarities and differences between BaTi2Sb2O and the cuprate and iron pnictide superconductors are discussed.