Coal fly ash (CFA) obtained from pulverized coal furnaces is a highly refractory waste that can be used for alumina and rare-earth elements (REEs) extraction. The REEs in this type of CFA are associated with a mullite and amorphous glassy mass that forms a core-shell structure. In this research, it was shown that complete dissolution of amorphous aluminosilicates from the mullite surface with the formation of the low-alkali mullite concentrate prior to sulfuric acid leaching with the addition of (NH4)2SO4 helps to accelerate the extraction of REEs. The extraction degree of Sc and other REEs reaches 70–80% after 5 h of leaching at 110 °C and acid concentration of 5 M versus less than 20% for the raw CFA at the same conditions. To study the leaching kinetics of the process, the effects of temperature (90–110 °C), liquid-to-solid ratio (5–10), and leaching time (15–120 min) on the degrees of Al and rare-earth elements (REEs) extraction were evaluated. After 120 min of leaching at 110 °C and L/S ratio = 10, the extraction of Al was found to be lower than 30%. At the same time, total REEs (TREE) and Fe extraction were greater than 60%, which indicates that a part of the TREE was transferred into the acid soluble phase. After leaching, the residues were studied by laser diffraction (LD), X-ray diffraction (XRD), X-ray fluorescence (XRF), and scanning electron microscopy (SEM-EDS) to evaluate the leaching mechanism and the solubility of Al- and Fe-containing minerals, such as mullite, hematite, and amorphous aluminosilicate.