Two common waste materials, red mud and fly ash, were used to produce a new nano-hybrid adsorbent by heat treatment with alkali addition. The new zeolitic structure formation of the hybrid adsorbent was revealed using the BET surface area, XRD, and SEM analyses. This hybrid adsorbent was utilized to remove arsenic from synthetic and real waste waters by batch and column adsorption experiments. The parameters such as the pH, contact time, and effect of the co-existing ions were investigated. Slightly acidic media favored arsenic adsorption by the hybrid adsorbent, the same as the individual use of fly ash and red mud. The effects of ions such as Fe3+, Cu2+, Cl-, SO42-, and PO43- were investigated as the co-existing ions. It was found that arsenic adsorption increased with cationic ions and decreased with anionic ions according to their valance charge. The intra-particle diffusion model showed that adsorption took place at three different rates depending on time. The hybrid adsorbent was formed as a pellet and utilized in a column for treatment of arsenic containing real waste water. The hybrid adsorbent derived from mineral wastes was more successful than their individual usages.