The phase mineralogy and leaching characteristics of some Indian coal fly ashes were studied to assess their safe disposal in abandoned coal mines. Since, fly ash contains a number of toxic trace elements, the leaching of fly ash was tested using strong acid/alkali solutions and distilled water under different conditions (solid-liquid ratio, leaching time, pH) in the temperature range of 30–100 °C. It was found that the concentration of various metals in leachates depends on their chemical nature, association with mineral phases of ash and follows the almost similar concentration profile to that of iron, especially in acidic medium. The distribution of toxic trace elements in fly ash and their leachability were found to depend on the amount of unburnt carbon and iron in fly ash. In alkaline medium, leaching of iron and toxic trace elements (except As) from fly ash was very negligible. Hence, alkali treatment of coal fly ash is desirable for its safe use in refilling of coal mines.