Hazardous heavy metal-laden coal combustion byproducts exposed to precipitation or surface/groundwater are of environmental concern. This study analyzed fly ash (FA) and desulfurization gypsum (FGD gypsum) samples obtained from 16 coal-fired power plants in Guizhou Province, China. A combination of field and laboratory studies was used to investigate the binding forms of lead (Pb), cadmium (Cd), and chromium (Cr) and their leaching characteristics under natural storage conditions. The results showed that there were significant proportions of residual states of these elements in FA (84–99% for Pb, 83–91% for Cd, and 73–97% for Cr), indicating a lack of migration to other environmental media. FGD gypsum contained high proportions of metals in migratable states, but the environmental risks were low due to their very low concentrations. The release of Pb, Cd, and Cr from FA and FGD gypsum into extracts varied according to pH. This is related to the form of each element in the solid and the series of reactions that occurs during the leaching process. However, aside from Cr in FA, all heavy metals in FA and FGD gypsum samples were present in concentrations below the relevant standards for landfill leachate, indicating very low release rates. The Cr levels (206–273 μg/L) in some of the FA extracts were higher than the limits for water pollution from domestic landfill, indicating that Cr in FA poses a leaching risk. The results of field leachate sampling and indoor simulated rainfall experiments further validated these findings, indicating that the release of Cr from stockpiled coal FA is a cause for concern.