The electrodeposition of Pt on RuO2(110) from acid solutions of several Pt complexes was studied using programmed potential step or potential sweep methods. The RuO2(110) single-crystal surface was obtained by gas-phase oxidation of Ru(0001). The electrodeposition process is characterized by a large crystallization overpotential and three-dimensional growth from a Pt adlayer. The mismatch between the RuO2(110) and Pt lattices is the likely origin of that overpotential. The nucleation is instantaneous, as verified by potential step experiments. The process starts with depositing a 0.25 ML of Pt, with Pt atoms arranged in a c(2 x 2) array, which is followed by the growth of Pt islands and three-dimensional clusters as in the Stranski-Krastanov growth mode. Density functional theory calculations were used to help in elucidating atomically resolved electrochemical scanning tunneling microscopy (ECSTM) images of the initial stages of Pt deposition. A Pt adlayer on RuO2(110) has lower catalytic activity for the oxygen reduction reaction compared to Pt, which is in agreement with a large calculated upshift of the d-band center of a low-coverage Pt deposit on RuO2(110) as well as a lack of the oxygen adsorption in a bridge configuration on that surface.