Aided phytostabilization using a combination of compost, zerovalent iron grit and coal fly ash (CZA) amendments and revegetation effectively promoted the biological recovery of mining spoils generated at a gold mine in Portugal. Selective dissolution of spoil samples in combination with solid phase characterization using microbeam X-ray absorption near edge structure (μXANES) spectroscopy and microbeam X-ray fluorescence (μXRF) mapping were used to assess As associations in spoils ten years after CZA treatment. The results show that As preferentially associates with poorly crystalline Fe-oxyhydroxides as opposed to crystalline Fe-(oxyhydr)oxide phases. The crystalline Fe(III)-phases dominated in the treated spoil and exceeded those of the untreated spoil three-fold, but only 2.6–6.8% of total As was associated with this fraction. Correlation maps of As:Fe reveal that As in the CZA-treated spoils is primarily contained in surface coatings as precipitates and sorbates. Arsenic binding with poorly crystalline Fe-oxyhydroxides did not inhibit As uptake by plants.