We report the vibrational spectra of the carbonyl complexes of anionic gold clusters in the range of the CO stretching frequency as measured in the gas phase using IR multiple photon dissociation spectroscopy. The investigated complexes contain between 3 and 14 Au atoms and up to 7 CO ligands. Special attention is given to the complexes that exhibit saturation CO coverage as well as to the monocarbonyl species. In conjunction with data from the corresponding cationic complexes we quantify how the CO stretching frequency varies with the charge state of the gold cluster. Our results provide a size- and charge-dependent basis to interpret values of the CO stretching frequency measured for CO on deposited gold clusters in terms of the char-e states of the clusters.