Pd-TiO2 catalysts with five Pd loadings were synthesized using a flame aerosol reactor. Their initial and changed catalytic properties and kinetic characteristics during/for O2 removal with CH4 were investigated. Different Pd loadings affected the size of Pd sub-nano clusters/nanoparticles and the speciation fraction of Pd (metallic Pd, PdO and PdOx (0〈x〈1)). Increased size of Pd nanoparticles on catalysts’ surface due to sintering and the reduction of PdO to metallic Pd or/and PdOx were observed during the reaction. Fractions of the total surface area of Pd species were calculated, and correlations to the apparent reaction rate constants were established. Apparent kinetic constants were linearly proportional to fractions of total surface areas of metallic Pd or/and reduced Pd oxide were revealed, representing the intrinsic active site. The linear correlation between the O2 reaction rate and the CO2 concentration in the initial gas stream was also observed due to an autocatalytic reaction effect.