The initial nucleation and the subsequent growth of Co on Au(111) have been studied with scanning tunneling microscopy. At low coverage the cobalt nucleates forming polygonal islands whose location and spacing are determined by the underlying Au(111) zigzag reconstruction geometry. The islands are two atomic layers high and grow laterally with increasing coverage. A model for the nucleation and growth is proposed and a comparison with the growth of other metals on gold is given. We also qualitatively relate our structural results to published magnetic measurements. © 1991 The American Physical Society.