Many phase transformations associated with solid-state precipitation look structurally simple, yet, inexplicably, take place with great difficulty. A classic case of difficult phase transformations is the nucleation of strengthening precipitates in high-strength lightweight aluminium alloys. Here, using a combination of atomic-scale imaging, simulations and classical nucleation theory calculations, we investigate the nucleation of the strengthening phase θ' onto a template structure in the aluminium-copper alloy system. We show that this transformation can be promoted in samples exhibiting at least one nanoscale dimension, with extremely high nucleation rates for the strengthening phase as well as for an unexpected phase. This template-directed solid-state nucleation pathway is enabled by the large influx of surface vacancies that results from heating a nanoscale solid. Template-directed nucleation is replicated in a bulk alloy as well as under electron irradiation, implying that this difficult transformation can be facilitated under the general condition of sustained excess vacancy concentrations.