The adsorption profiles and electronic structures of Pt-n(n = 1-4) clusters on stoichiometric, reduced and reconstructed rutile TiO2(110) surfaces were systematically studied using on site d-d Coulomb interaction corrected hybrid density-functional-theory (DFT) calculations. The atomic structure of small Pt cluster adsorbates mainly depends on the stoichiometry of the corresponding titania support. The cluster shapes on the bulk terminated ideal surface look like their gas phase low-energy structures. However, for instance, they get significantly distorted on the reduced surfaces with increasing oxygen vacancies. On nonstoichiometric surfaces, Pt-Ti coordination becomes dominant in the determination of the adsorption geometries. The electronic structure of Pt-n/TiO2(110) systems cannot be correctly described by pure DFT methods, particularly for nonstoichiometric cases due to the inappropriate treatment of the correlation for d electrons. We performed DFT + U calculations to give a reasonable description of the reconstructed rutile (110) surface. Pt clusters induce local surface relaxations that influence band edges of titania support and bring a number of band-gap states depending on the cluster size. Significant band gap narrowing occurs upon Pt-n-surface interaction due to adsorbate driven states on the bulk terminated and reduced surfaces. On the other hand, they give rise to a band-gap widening associated to partial reoxidation of the reconstructed surface. No metallization arises even for Pt-4 on rutile.