Understanding the behavior of a polaron in contact with water is of significant importance for many photocatalytic applications. We investigated the influence of water on the localization and transport properties of polarons at the rutile (110) surface by constrained density functional theory. An excess electron at a dry surface favors the formation of a small polaron at the subsurface Ti site, with a preferred transport direction along the [001] axis. As the surface is covered by water, the preferred spatial localization of the polarons is moved from the subsurface to the surface. When the water coverage exceeds half a monolayer, the preferred direction of polaron hopping is changed to the [110] direction toward the surface. This characteristic behavior is related to the Ti3d-orbital occupations and crystal field splitting induced by different distorted structures under water coverage. Our work describes the reduced sites that might eventually play a role in photocatalysis for rutile (110) surfaces in a water environment.