Au catalysts with loadings of 1.5 and 3 wt% were dispersed over CeO2 and Co (9; 12 mol%) promoted CeO2, using the deposition–precipitation method, followed by calcination at 350 °C. The fresh supported Au catalysts were characterized using several techniques in order to investigate their morphological, structural and redox properties before being tested for formaldehyde (HCHO) total oxidation. All of the supported Au catalysts exhibited HCHO oxidation into CO2 at 25 °C and demonstrated a great stability for the time on stream (40 h). The 3 wt% Au catalysts demonstrated a higher HCHO conversion than their low-gold counterparts (1.5 wt% Au), a remarkable improvement in the HCHO conversion was observed using Co-promoted ceria (9 mol%). Based on the HCHO amount (in μmol) converted into CO2 per gram of gold per second after 40 h on stream, the 1.5Au/CeCo catalyst demonstrated the best activity (∼3.9) as compared to the other catalysts (≤2.0). X-ray photoelectron spectroscopy (XPS) characterization of the fresh catalysts indicated that the Au species were mainly in a slightly ionic δ+ valence state, but did not exclude the possibility of metallic gold. Furthermore, no marked changes were found in gold dispersion upon adding cobalt. Promotion of the HCHO oxidation over gold supported on Co-promoted ceria catalysts can be related to the higher concentration of oxygen vacancies and an improvement in the redox properties, which can contribute to the better activation of O2 and an enhancement of the oxygen mobility.