Despite extensive studies of transition metal (TM) clusters supported on ceria (CeO2), fundamental issues such as the role of the TM atoms in the change in the oxidation state of Ce atoms are still not well understood. In this work, we report a theoretical investigation based on static and ab initio molecular dynamics density functional theory calculations of the interaction of 13-atom TM clusters (TM = Pd, Ag, Pt, Au) with the unreduced CeO2(111) surface represented by a large surface unit cell and employing Hubbard corrections for the strong on-site Coulomb correlation in the Ce f-electrons. We found that the TM13 clusters form pyramidal-like structures on CeO2(111) in the lowest energy configurations with the following stacking sequence, TM/TM4/TM8/CeO2(111), while TM13 adopts two-dimensional structures at high energy structures. TM13 induces a change in the oxidation state of few Ce atoms (3 of 16) located in the topmost Ce layer from Ce(IV) (itinerant Ce f-states) to Ce(III) (localized Ce f-states). There is a charge flow from the TM atoms to the CeO2(111) surface, which can be explained by the electronegativity difference between the TM (Pd, Ag, Pt, Au) and O atoms, however, the charge is not uniformly distributed on the topmost O layer due to the pressure induced by the TM13 clusters on the underlying O ions, which yields a decrease in the ionic charge of the O ions located below the cluster and an increase in the remaining O ions. Due to the charge flow mainly from the TM8-layer to the topmost O-layer, the charge cannot flow from the Ce(IV) atoms to the O atoms with the same magnitude as in the clean CeO2(111) surface. Consequently, the effective cationic charge decreases mainly for the Ce atoms that have a bond with the O atoms not located below the cluster, and hence, those Ce atoms change their oxidation state from IV to III. This increases the size of the Ce(III) compared with the Ce(IV) cations, which builds-in a strain within the topmost Ce layer, and hence, also affecting the location of the Ce(III) cations and the structure of the TM13 clusters.