We report scanning tunneling microscopy observations of Ge deposited on the Si(111)-(7 x 7) surface for a sequence of submonolayer coverages. We demonstrate that Ge atoms replace so-called Si adatoms. Initially, the replacements are random, but distinct patterns emerge and evolve with increasing coverage, until small islands begin to form. Corner adatom sites in the faulted half unit cells are preferred. First-principles density functional calculations find that adatom substitution competes energetically with a high-coordination bridge site, but atoms occupying the latter sites are highly mobile. Thus, the observed structures are indeed more thermodynamically stable.