The gas-phase reaction of size-selected Ru(n)(+) (n = 4-6) clusters with CO in an ion trap yields only one specific ruthenium carbonyl complex for each cluster size, Ru4(CO)14(+), Ru5(CO)16(+), and Ru6(CO)18(+). First-principles density functional theory calculations reveal structures for these hitherto unknown carbonyl compounds that are in perfect agreement with the geometries predicted by Wade's electron counting rules. Furthermore, reactions with D2 show that for Ru4(+) and Ru6(+), CO molecules can be partially replaced by D2 to form hydrido carbonyl complexes while preserving the total ligand count corresponding to the Wade cluster sizes.