Elevated Cr and Mo concentrations are often found in leachates of thermally treated solid waste, but there is no general explanation for this so far. Therefore, we studied the leaching behaviour after thermal treatment as a function of heating temperature and residence time for two types of solid waste: contaminated sludge and bottom ash from municipal solid waste incineration. The leaching behaviour of both waste streams was compared with experiments on synthetic samples, allowing deduction of a general mechanism for Cr and Mo leaching. Cr and Mo showed a similar leaching behaviour: after an initial increase, the leaching decreased again at higher temperatures. Oxidation of these elements from their lower oxidation states to chromate and molybdate at temperatures up to 600 °C was responsible for the increased leaching. At higher temperatures, both Mo and Cr leaching decreased again owing to the formation of an amorphous phase, incorporating the newly formed chromate and molybdate salts, which prevents them from leaching.