Nanosized Cu–Mn composite oxide catalysts were prepared from potassium permanganate, copper nitrate, n-butanol, and cetyltrimethylammonium bromide as a manganese source, copper source, reducing agent, and surfactant, respectively. The Cu0.2–Mn sample possessed a small particle size (10–40nm) and a relatively high specific surface area (46.24m2⋅g−1); its main components were Cu1.5Mn1.5O4 and Mn3O4. As a consequence, the Cu0.2–Mn catalyst exhibited good catalytic activity in the oxidation of toluene. At a toluene concentration of 1000ppm and a space velocity of 60,000mL⋅g−1⋅h−1, the T50 and T90 of the Cu0.2–Mn catalyst toward toluene were 239∘C and 250∘C, respectively. Furthermore, even after 30h of operation at 275∘C, the conversion of toluene was 99% (at the space velocity of 60,000mL⋅g−1⋅h−1).