In the present work, we predict the stable composition and structures of CeMOx clusters at realistic temperatures and oxygen pressures. Density functional theory (DFT+U) combined with ab initio evolution algorithm (USPEX) is used to find the global minimum structures of CeMOx. The phase diagram of CeMOx at different temperature and pressure is derived using ab initio atomistic thermodynamic method. Initially, oxygen atom prefers to locate on the outside of the CeM core cluster and the sequential oxidation of CeM core is found. The nonstoichiometric clusters exhibit peculiar magnetic behavior, suggesting the possibility of tuning magnetic properties by changing environmental pressure and temperature conditions. These clusters provide novel model systems to understand the catalytic properties of ceria in many reactions.