We demonstrate the formation of complexes involving attractive interactions between D and CO on Ru(0001) that are stable at significantly higher temperatures than have previously been reported for such intermediate species on this surface. These complexes are evident by the appearance of new desorption features upon heating of the sample. They decompose in stages as the sample temperature is increased, with the most stable component desorbing at > 500 K. The D:CO ratio remaining on the surface during the final stages of desorption tends towards 1:1. The new features are populated during normally incident molecular beam dosing of D-2 on to CO pre-covered Ru(0001) surfaces (180 K) when the CO coverage exceeds 50% of the saturation value. The amount of complex formed decreases somewhat with increasing CO pre-coverage. It is almost absent in the case of dosing on to the fully saturated surface. The results are interpreted in terms of both local and long-range rearrangements of the overlayer that give rise to the observed CO coverage dependence and limit the amount of complex that can be formed. (C) 2012 American Institute of Physics. [http://dx.doi.org/10.1063/1.3689553]