First-principle calculations are employed to show that the magnetic structure of small atomic clusters of Co, formed on a crystalline W(110) surface and containing 3-12 atoms, strongly deviates from the usual stable ferromagnetism of Co in other systems. The clusters are ferri-, ferro- or non-magnetic, depending on cluster size and geometry. We determine the atomic Co moments and their relative alignment, and show that antiferromagnetic spin alignment in the Co clusters is caused by hybridization with the tungsten substrate and band filling. This is in contrast with the typical strong ferromagnetism of bulk Co alloys, and ferromagnetic coupling in Fe/W(110) clusters.