Nanostructured materials based on CeO2 and Pt play a fundamental role in catalyst design. However, their characterization is often challenging due to their structural complexity and the tendency of these materials to change under reaction conditions. In this work, we combine calculations based on the density functional theory, a machine-learning assisted global optimization method, and ab initio thermodynamics to characterize stable oxidation states of ceria-supported PtyOx particles under different environmental conditions. The collection of global minima structures for different stoichiometries resulting from the global optimization effort is used to assess the effect of temperature, oxygen pressure, and support interactions on the phase diagrams, oxidation states, and geometries of the PtyOx particles. We, thus, identify favored structural motifs and O:Pt ratios, revealing that oxidized states of freestanding and ceria-supported platinum particles are more stable than reduced ones under a wide range of conditions. These results indicate that studies rationalizing activity of ceria-supported Pt clusters must consider oxidized states and that previous understanding of such materials obtained only with fully reduced Pt clusters may be incomplete.