We have synthesized a new oxypnictide, Ba2Ti2Fe2As4O, via a solid-state reaction under a vacuum. The compound crystallizes in a body-centered tetragonal lattice, which can be viewed as an intergrowth of BaFe2As2 and BaTi2As2O, thus containing Fe2As2 layers and Ti2O sheets. Bulk superconductivity at 21 K is observed after annealing the as-prepared sample at 773 K for 40 h. In addition, an anomaly in resistivity and magnetic susceptibility around 125 K is revealed, suggesting a charge- or spin-density wave transition in the Ti sublattice.