This study is the first investigation on the encapsulation of red mud by a polysulfone matrix through a phase inversion process to obtain composite capsules for the removal of fluoride from aqueous solutions. This approach facilitates the use of red mud in batch and column sorption techniques because the polysulfone matrix renders efficient aqueous diffusivity. The produced polysulfone-red mud composite capsules (red mud@PSF capsules) were characterized by using FT-IR, TGA, SEM and BET. The batch sorption experiments showed that the red mud@PSF capsules prepared with a mass ratio of red mud to polysulfone (1:1, g:g) provided maximum removal at equilibrium pH between 3.2 and 4.7. The batch equilibrium was attained within 30 minutes and sorption behavior was governed by pseudo-second-order kinetics together with intra-particle diffusion. Isotherm analyses showed that the Freundlich and Redlich-Peterson isotherm models better represented the sorption data, which was confirmed by the Chi-square (χ2) statistical test. The capsules could be reused for at least two sorption-desorption cycles without significant change in their sorption efficiency. Batch and column experiments on a real mineral water sample fortified with fluoride (final concentration 10 mg L-1) showed that the red mud@PSF capsules could be applied to real water samples to reduce the fluoride concentration below the limit value (1.5 mg L-1) recommended by the World Health Organization (WHO) for drinking water.