In order to identify the stable structures and oxidation states of ceria-supported Pt particles, we therefore combine a novel global optimization method with ab initio thermodynamics. We focus on the characterization of prevailing structural motifs, the effects of conditions on the stability of different oxidation states, and the role of the ceria support. In particular, we use a machine-learning assisted algorithm for the exploration of the configurational space. Once the most stable structures have been determined for the targeted stoichiometries, their Gibbs Free energy of formation is evaluated under varying conditions by means of ab Initio thermodynamics (AITD). A consistent picture emerges for the formation and oxidation of both free-standing and ceria-supported PtOx particles, revealing support-effects on the structural and compositional properties of PtOx clusters, and the changes induced by exposure to different environmental conditions. Oxidized states of PtOx clusters are found to be prevalent under a wide range of reaction conditions.