One-dimensional nanocrystals favoring efficient charge transfer have attracted enormous attentions, and conductive nanobelts of black titania with a unique band structure and high electrical conductivity would be interestingly used in electrocatalysis. Here, Pd nanodots supported by two kinds of black titania, the oxygen-deficient titania (TiO2-x) and nitrogen-doped titania (TiO2-x:N), were synthesized as efficient composite catalysts for oxygen-reduction reaction (ORR). These composite catalysts show improved catalytic activity with lower overpotential and higher limited current, compared to the Pd nanodots supported on the white titania (Pd/TiO2). The improved activity is attributed to the relatively high conductivity of black titania nanobelts for efficient charge transfer (CT) between Ti3+ species and Pd nanodots. The CT process enhances the strong metal-support interaction (SMSI) between Pd and TiO2, which lowers the absorption energy of O-2 on Pd and makes it more suitable for oxygen reduction. Because of the stronger interaction between Pd and support, the Pd/TiO2-x:N also shows excellent durability and immunity to methanol poisoning.