Plants regularly experience suboptimal environments, but this can be particularly acute on highly disturbed mine sites such as the extensive coal mine spoils in central New Brunswick. Willows have proven to be very effective invaders and colonizers of such highly disturbed areas. Two North American willows—Salix discolor Muhl. (DIS) and S. eriocephala Michx. (ERI)—were artificially established in common-garden field tests on two adjacent coal mine spoil sites: one with high clay content and a very low pH (3.6), the other consisting of shale overburden and a neutral pH (6.8). Both willows showed large variation among genotypes within each species in foliar concentrations of heavy metals, and some clones of DIS and ERI had up to 16 times the iron and aluminum uptake on the acidic site vs. the adjacent overburden. Genetic selection among species and genotypes may be useful for reclamation activities aimed at reducing specific metal concentrations on abandoned mine sites. Results showed that the greater acidity of the clay site resulted in greater metal mobility and availability for uptake by plants. Despite the high metal uptake and content in these plants, they showed no foliar symptoms of metal toxicity. Phytoremediation efforts aimed at reclaiming potentially toxic mine sites require plants that can tolerate such harsh and toxic conditions. Strong clonal variation among the 15 clones tested from these two willows suggests that selection and breeding for willow clones with special capacities for uptake of heavy metals from moderately contaminated sites looks very promising; especially in the case of ERI, which can take up high concentrations of metals without showing adverse effects on growth.