A lack of information regarding which ecological factors influence restoration success or failure has hindered scientifically based restoration decision-making. We focus on one headwater site to examine factors influencing divergent ecological outcomes of two post-mining stream restoration projects designed to improve instream conditions following 70 years of mining impacts. One project was designed to simulate natural stream conditions by creating a morphologically complex channel with high habitat heterogeneity (HH-reach). A second project was designed to reduce contaminants and sediment using a sand filter along a straight, armored channel, which resulted in different habitat characteristics and comparatively low habitat heterogeneity (LH-reach). Within 2 years of completion, stream habitat parameters and community composition within the HH-reach were similar to those of reference reaches. In contrast, habitat and community composition within the LH-reach differed substantially from reference reaches, even 7–8 years after project completion. We found that an interaction between low gradient and high light availability, created by the LH-reach design, facilitated a Chironomid-Nostoc mutualism. These symbionts dominated the epilithic surface of rocks and there was little habitat for tailed frog larvae, bioavailable macroinvertebrates, and fish. After controlling for habitat quantity, potential colonizing species’ traits, and biogeographic factors, we found that habitat characteristics combined to facilitate different ecological outcomes, whereas time since treatment implementation was less influential. We demonstrate that stream communities can respond quickly to restoration of physical characteristics and increased heterogeneity, but “details matter” because interactions between the habitats we create and between the species that occupy them can be complex, unpredictable, and can influence restoration effectiveness.