Coal fly ash (CFA), a by-product generated from coal-burning power plants, readily leaches toxic elements into aquatic environments. The present study describes a classification system for CFA based on the chemical composition of CFA and leachability of toxic elements, which can promote the safe and effective utilization of CFA for uses such as fly ash cement. To classify CFA samples, the CaO content, leachate pH, leachability of toxic elements such as B, As, and Se, and the acid- and alkali-soluble Si and Al in glassy components were determined for ten types of CFA samples produced in Japan. The results indicated that the CFA samples could be grouped into three groups: group A, which was characterized by low CaO content, low leachate pH, and a relatively high amount of alkaline-soluble Al; group B, which was characterized by low CaO content, low leachate pH, and relatively low amount of alkaline-soluble Al; and group C, which was characterized by high CaO content, high leachate pH, and relatively low amount of alkaline-soluble Al. Characteristic of group A CFA was the simultaneous leaching of Al and the minor elements along with a gradual increase in pH. This type of CFA carries the risk of leaching toxic substances upon contact with alkali solutions. These results can aid the discovery and separation of safe and unsafe CFA, allowing the safe CFA to be used in cement to produce concrete under alkali conditions.