The doping of CeO2 with trivalent cations is a common technique for enhancing ionic conductivity in electrolytes for solid oxide fuel cell applications. However, the local defect structure in these materials is yet to be fully explored. Furthermore, many studies have overlooked the effect of the dopants on the reducibility of CeO2, which is important as electronic conductivity can short-circuit the fuel cell. Density functional theory (DFT)+U calculations have been performed on a series of CeO2 systems doped with trivalent cations. The most stable configuration and the relative attraction between dopant cations and oxygen vacancies were determined, and it was found that the defect structure is principally dependent on the ionic radius of the dopant cations. The reduction energy was found to be dependent on the structure around the dopants but did not vary significantly between dopants of similar ionic radii. From these results, it is possible to suggest which trivalent cations would be most suitable to enhance ionic conductivity without increasing electronic conductivity in solid oxide fuel cell electrolytes.