Using low-energy electron microscopy, we find that Cu and Pb, arranged in single atomic layers on the Cu(111) surface, self-assemble into ordered, nanoscale domain patterns. The pattern type, feature size, and degree of long-range order vary controllably with surface composition and temperature. The continuous evolution of the domain structures from circular islands to stripes to 'inverted' islands with increasing Pb coverage agrees with theoretical predictions and simulations based on the existence of competing long- and short-range interactions. The details of the self-assembly process depend on a number of factors including temperature, surface morphology, and the presence of small amounts of sulfur.