Tb-doped CeO2 (ceria) is a promising mixed conductor for oxygen permeation membranes and reversible oxygen sorbents. To predict solubility of Tb ions in ceria for a wide range of concentrations, density functional theory (DFT + U) calculations with two different values of Hubbard U-parameter on Tb and Ce ions were combined with alloy thermodynamics and the Concentration Wave approach. It is shown that, to predict properties of disordered solid solutions at finite temperatures, the energy parameters in the mixing energies can be extracted from the DFT + U calculations performed at T = 0 K for two ordered configurations of the dopant in the supercells. The unlimited solubility of Tb4+ in CeO2 in the quasi-binary cross-section CeO2-TbO2 is predicted in the temperature range where both stoichiometric TbO2 and CeO2 reveal fluorite structures (above 700 degrees C).