Bauxite residue (or red mud) is a waste generated during the Bayer process of alumina production. Its storage is a spatial and environmental concern. Currently, there are no bulk applications of bauxite residue except for minor use in cements and ceramics. Nonetheless, some types of bauxite residues are rich in rare-earth elements (REEs), and the extraction of scandium in particular is of special interest. Leaching experiments on Greek bauxite residue were performed with different acids at different concentrations, liquid-to-solid ratios, leaching times and temperatures. Extraction of the REEs was high for leaching in HCl solutions compared to other acids, but the dissolution of iron was high as well (60%). The maximum extraction of the REEs was around 80%. Sodium and calcium were completely dissolved during leaching. Dissolution of aluminum, silicon and titanium was between 30% and 50%. The leaching data show a very close association of scandium with the iron oxide phases.