The adsorption and diffusion of potassium and oxygen on Rh(110), as well as the coadsorption of K and O and its effect on K diffusion, have been studied using periodic density functional theory (DFT) calculations (PW91-GGA). On both the nonreconstructed (1 x 1) and the missing-row (MR) reconstructed surfaces, O prefers the short bridge site at low coverage, with a binding energy of ca. -5.2 eV at (1)/(4) ML. At theta(O) > (1)/(2) ML, O atoms occupy alternating threefold sites along the ridge and form a zigzag pattern. Interaction with the ridge sites is enhanced by the MR reconstruction. Potassium prefers to be in the trough, with a binding energy of -2.3 eV on the (1 x 1) surface and -2.9 eV on the MR surface at (1)/(8) ML. Thus, the adsorption of both O and K at low to medium coverage promotes the MR reconstruction. The coadsorption of K and O enhances the binding energy of K to a maximum of -3.6 eV at the highest oxygen coverage studied, 1(3)/(8) ML. Oxygen adsorption is also stabilized by K, though to a smaller extent on a per-O-atom basis. On both surfaces, K prefers to diffuse in the [1 (1) over bar0] direction with a barrier of ca. 0.05 eV. Oxygen diffusion also prefers the [1 (1) over bar0] direction on the MR surface but is not clearly anisotropic on the (1 x 1) surface. The barrier to O diffusion ranges from 0.6-0.8 eV depending on the coverage and reconstruction. In the presence of coadsorbed O, the diffusion barrier of K tops out at ca. 0.12 eV, much lower than earlier estimates based on mean-field models. Possible reasons for this apparent contradiction are discussed.