The modification of cerium dioxide with nanoscale metal clusters is intensely researched for catalysis applications, with gold, silver, and copper having been particularly well studied. The interaction of the metal cluster with ceria is driven principally by a localised interaction between a small number of metal atoms (as small as one) and the surface and understanding the fundamentals of the interaction of metal atoms with ceria surfaces is therefore of great interest. Much attention has been focused on the interaction of metals with the (111) surface of ceria, since this is the most stable surface and can be grown as films, which are probed experimentally. However, nanostructures exposing other surfaces such as (110) show high activity for reactions including CO oxidation and require further study; these nanostructures could be modified by deposition of metal atoms or small clusters, but there is no information to date on the atomic level details of metal-ceria interactions involving the (110) surface. This paper presents the results of density functional theory (DFT) corrected for on-site Coulomb interactions (DFT+U) calculations of the adsorption of a number of different metal atoms at an extended ceria (110) surface; the metals are Au, Ag, Cu, Al, Ga, In, La, Ce, V, Cr, and Fe. Upon adsorption all metals are oxidised, transferring electron(s) to the surface, resulting in localised surface distortions. The precise details depend on the identity of the metal atom. Au, Ag, Cu each transfer one electron to the surface, reducing one Ce ion to Ce(3+), while of the trivalent metals, Al and La are fully oxidised, but Ga and In are only partially oxidised. Ce and the transition metals are also partially oxidised, with the number of reduced Ce ions possible in this surface no more than three per adsorbed metal atom. The predicted oxidation states of the adsorbed metal atoms should be testable in experiments on ceria nanostructures modified with metal atoms.