Understanding strong metal‐support interactions is crucially important for developing atom‐efficient transition metal heterogeneous catalysts. Herein, we performed a density functional theory study of highly dispersed Pt on CeO2(110). Various surface models are compared in terms of thermodynamic stability, electronic properties and energy diagrams for CO oxidation. Pt prefers square‐planar oxygen coordination in all models with a +2 state. The structures with a single Pt atom exhibit a low CO oxidation activity. A higher activity is predicted by replacement of a surface Ce by two Pt atoms. The high activity of this highly stable structure stems from the coordinative unsaturation of one of the Pt atoms and the presence of a neighboring two‐fold O atom. The CO oxidation occurs via a Mars‐van Krevelen mechanism. A compared to single‐atom catalysts based on Pt in interaction with CeO2(111) emphasizes the strong dependence of catalytic activity on the ceria surface termination. Single‐atom catalysis: A high activity of low‐temperature CO oxidation is predicted by replacement of a surface Ce of CeO2(110) by two Pt atoms, and the compared to single‐atom catalysts based on Pt in interaction with CeO2(111) emphasizes the strong dependence of catalytic activity on the ceria surface termination.