In this work, we present material chemistry in the hydrothermal synthesis of new complex structure materials based on various dosage ratios of Fe and Ce (1:0, 2:1, 1:1, 1:2, 0:1), characterize them by the relevant methods that allow characterization of both crystalline and amorphous phases and correlate their structure/surface properties with the adsorptive performance of the five toxic anions. The applied synthesis conditions resulted in the formation of different compounds of Fe and Ce components. The Fe-component was dominated by various phases of Fe hydrous oxides, whereas the Ce-component was composed of various phases of Ce carbonates. The presence of two metal salts in raw materials resulted in the formation of a mesoporous structure and averaged the surface area compared to one metal-based material. The surface of all Fe-Ce composites was abundant in Fe component phases. Two-metal systems showed stronger anion removal performance than one-metal materials. The best adsorption was demonstrated by Fe-Ce based materials that had low crystallinity, that were rich in phases and that exhibited surfaces were abundant in greater number of surface functional groups. Notably, Fe extended fine structures simulated by EXAFS in these better adsorbents were rich from oscillations from both heavy and light atoms. This work provides new insights on the structure of composite inorganic materials useful to develop their applications in adsorption and catalysis. It also presents new inorganic anion exchangers with very high removal potential to fluoride and arsenate.