We present the phase diagram of Ce1-xGdxO2-x/2 (CGO), calculated by means of a combined Density Functional Theory (DFT), cluster expansion and lattice Monte Carlo approach. We show that this methodology gives reliable results for the whole range of concentrations (x ≡ xGd ≤ 1). In the thermodynamic equilibrium, we observe two transitions: the onset of oxygen-vacancy (O-Va) ordering at ca. 1200-3300 K for concentrations xGd = 0.3-1, and a phase separation into CeO2 and C-type Gd2O3 occurring below ca. 1000 K for all concentrations. We also model 'quenched' systems, with cations immobile below 1500 K, and observe that the presence of random-like cation configurations does not prevent C-type vacancy ordering. The obtained transition temperatures for Va ordering agree rather well with existing experimental data. We analyse the effect of vacancy ordering and composition on the lattice parameters and relaxation pattern of cations.