The use of waste materials from mineral ore processing has much potential for immobilizing pollutants such as arsenic (As) in natural soils and waters. The purpose of the present study was to investigate red mud (RM, a finely textured bauxite-ore residue) as a sequestering agent for arsenate and phosphate, including characterization of the types of surface complexes formed. The mineralogical and structural changes occurring in RM were investigated after exchange with arsenate [As(V)-RM] and phosphate [P(V)-RM] anions at pH 4.0, 7.0, and 10.0. Eight different phases were present in the untreated red mud (RMnt), though 80 wt.% of the crystalline phase consisted of sodalite, hematite, gibbsite, and boehmite. The X-ray diffraction (XRD) data for As(V)-RM revealed an anion-promoted dissolution of the gibbsite, suggesting that this phase was the most active for As(V) sequestration. In addition, the lattice parameters of cancrinite were different in As(V)-RM at pH 7.0 and 10.0 from those in RMnt. The changes may be related to the incorporation of arsenate in the cancrinite cages. X-ray diffraction patterns of P(V)-RM at pH 4.0 and 7.0 revealed the dissolution of sodalite, hematite, and gibbsite, and the formation of a novel phase, berlinite [(α,β)AlPO4]. The new phases detected through XRD and thermal (TG/DTG) analysis in P(V)-RM probably originated through an initial phosphate-promoted dissolution of some RM phases, followed by a precipitation reaction between the phosphate and Al/Fe ions. The results obtained suggest that phosphate and arsenate, though with different reactivities, were strongly bound to some RM phases, such as gibbsite, cancrinite, sodalite, and hematite through mechanisms such as chemical sorption and coprecipitation reactions. The knowledge acquired will be helpful in selecting alternative materials such as red muds, which currently pose critical economic and environmental challenges related to their disposal, for the decontamination of soils and waters polluted with As.