Carbon-supported PtRu-MoOx nanoparticles with significant CO tolerance were prepared by a new two-step procedure: in the first step, molybdenum oxide was deposited on a carbon substrate (MoOx/C) by impregnation, and in the second one, Pt and Ru were incorporated following a colloidal method with NaHSO3. The composition, particle size, and crystallinity of the catalysts were determined by X-ray analytical methods (X-ray diffraction (XRD), X-ray photoelectron spectroscopy (XPS), and total-reflection X-ray fluorescence (TXRF)), transmission electron microscopy (TEM), and thermogravimetry (TG). Conventional electrochemical techniques such as cyclic voltammetry (CV) and chronoamperometry were applied in combination with spectroscopic methods adapted to the electrochemical systems for in situ studies, such as Fourier transform infrared spectroscopy (FTIRS) and differential electrochemical mass spectrometry (DEMS). The results of this work are highly encouraging, as it is proved that a reduction of the amount of precious metals Pt and Ru is possible in parallel with a significant increase of CO tolerance in comparison with commercial catalysts.