The physical and chemical properties of low-dimensional structures depend on their size and shape, and can be very different from those of bulk matter. If such structures have at least one dimension small enough that quantum-mechanical effects prevail, their behaviour can be particularly interesting. In this way, for example, magnetic nanostructures can be made from materials that are non-magnetic in bulk(1), catalytic activity can emerge from traditionally inert elements such as gold(2), and electronic behaviour useful for device technology can be developed(3,4). The controlled fabrication of ordered metal and semiconductor nanostructures at surfaces remains, however, a difficult challenge. Here we describe the fabrication of highly ordered, two-dimensional nanostructure arrays through nucleation of deposited metal atoms on substrates with periodic patterns defined by dislocations that form to relieve strain. The strain-relief patterns are created spontaneously when a monolayer or two of one material is deposited on a substrate with a different lattice constant. Dislocations often repel adsorbed atoms diffusing over the surface, and so they can serve as templates for the confined nucleation of nanostructures from adatoms. We use this technique to prepare ordered arrays of silver and iron nanostructures on metal substrates.