Removal of arsenic (As) from water by co-precipitation with Fe(III) (oxyhydr)oxides is a widely used technique in water treatment. Nevertheless, As removal efficiency appears to be sensitive to the composition of the water matrix. The aim of this study was to gain a deeper understanding of the independent and combined effects of silicate (Si), phosphate (P), natural organic matter (NOM) and calcium (Ca) on arsenate [As(V)] co-precipitation efficiency and the size of Fe(III) precipitates. We found that, in complex solutions, containing multiple solutes and high levels of Ca, (variations in) Si and P concentrations reduce As(V) removal to some extent, mainly due to a decreased adsorption of As(V) onto Fe(III) precipitates. On the other hand, NOM concentrations reduced As(V) removal to a much greater extent, due to possible formation of mobile Fe(III)–NOM complexes that were difficult to remove by filtration. These findings have a great significance for predicting As(V) removal as a function of seasonal and process-related water quality changes at water treatment plants.