The surface properties of carbon- and nitrogen-modified Mo(110) have been investigated using high-resolution electron energy loss spectroscopy, near-edge x-ray absorption fine structure, Auger electron spectroscopy, x-ray photoelectron spectroscopy, and temperature programmed desorption. Exposure of the Mo(110) surface to olefin molecules at 600 K resulted primarily in surface carbon atoms; subsequent annealing to 1200 K produced interstitial/subsurface carbon atoms. Higher concentrations of carbon atoms in the interstitial/subsurface regions could be achieved by repeated dosing/annealing cycles. Exposure to either N-2 or NH3 led to the deposition of surface nitrogen atoms. Subsequent annealing of such surfaces resulted in N-2 desorption without any detectable production of interstitial/subsurface nitrogen atoms. Reactions with ethylene or cyclopentene as probing molecules demonstrated that the reactivities of carbon- and nitrogen-modified Mo(110) depend strongly on the location of the adatoms. For example, Mo(110) surfaces modified primarily by surface carbon and nitrogen atoms are inert toward the dissociation of either ethylene or cyclopentene. In contrast, carbon-modified Mo(110) with interstitial/subsurface carbon atoms remains active toward the decomposition of these two molecules, although the decomposition pathways are altered from those on the clean Mo(110) surface.