CO adsorption on NO(2)-predosed Au[111] reveals an unexpected attractive coadsorbate interaction, associated with an unprecedented blueshift of the CO stretch frequency, a sizeable attenuation of the infrared NO(2) symmetric stretch band, and a (sq.rt(7) x sq.rt(7))R19 degrees structure characterized by scanning tunneling microscopy and low energy electron diffraction. Density functional calculations allow us to rationalize these observations, and point towards a general pattern of behavior for electronegative coadsorbates on coinage metals, with important implications for catalytic promotion.