This work presents experimental evidence for the natural attenuation of arsenic in semi-arid soils contaminated by wastes containing oxidized arsenic species. This evidence was obtained through measurements of water-soluble As in aqueous soil extracts of extensive soil sampling sets, and by comparing them with the solubility of the original As species in the wastes. Additionally, wet chemical analyses of total As, Pb, Zn, Cd, Cu, Mn, Fe, Ca, and pH, were conducted on these samples. Selected fine soil fractions of high total As content but low water-soluble As content were analyzed by Scanning Electron Microscopy coupled with Energy Dispersive X-ray Fluorescence Spectroscopy, and revealed predominant associations between As, Pb, and Zn, and little to none of As with Fe. This evidence suggests attenuation is due to formation of very low-solubility heavy metal-like arsenates as arsenic-containing wastes equilibrate with the soil media. Thermodynamic solubility calculations, using total elemental contents and data from pure heavy metal arsenates, further support this hypothesis.