A five-step sequential extraction (SE) procedure was used to investigate the leaching behaviour and geochemical partitioning of the trace elements As, Zn, Pb, Ni, Mo, Cr and Cu in a 20-year-old fly ash (FA) dump. The weathered FA, which was hydraulically co-disposed with salt laden brine in slurry form (FA: brine ratio of 1:5), was analyzed and compared with fresh FA. The weathered FA samples were collected from three cores, drilled at a coal-fired power station in the Republic of South Africa while the fresh FA sample was collected from the hoppers in the ash collection system at the power station. The FA samples were sequentially leached using: ultrapure water; ammonium acetate buffer solution (pH 7); ammonium acetate buffer solution (pH 5); hydroxylamine hydrochloride in nitric acid (pH 2) and finally the residues were digested using a combination of HClO4: HF: HNO3 acids. Digestion of as received (unleached) FA samples was also done using a combination of HClO4: HF: HNO3 acids in order to determine the total metal content. The trace element analysis was done using ICP-OES (Varian 710-ES). The SE procedure revealed that the trace elements present in the fresh FA and the weathered FA samples obtained from the three cores could leach upon exposure to different environmental conditions. The trace elements showed continuous partitioning between five geochemical phases i.e., water soluble fraction, exchangeable fraction, carbonate fraction, Fe and Mn fraction and residual fraction. Although the highest concentration of the trace elements (ranging 65.51%-86.34%) was contained in the residual fraction, a considerable amount of each trace element (ranging 4.42%-27.43%) was released from the labile phases (water soluble, exchangeable and carbonate fractions), indicating that the trace species readily leach from the dumped FA under environmental conditions thus pose a danger to the receiving environment and to groundwater.