In waste management, recycled and industrial aggregates (e.g., electric arc furnace (EAF) slags) for construction applications have to fulfil the limit values with respect to the total and/or leachable contents of potentially environmentally problematic chemical elements (PEPE, e.g., Cr, Ni, Cu, Mo, V). Natural aggregates, i.e., quarried hard rocks, are neither tested nor regulated for these parameters in most EU member states, e.g., Austria, prior to using them as a construction material. The purpose of this study was to relate the mineralogy to the leachability of natural aggregates with a special emphasis on PEPE and to interpret these findings in comparison with EAF slags. Five samples of Austrian rocks were investigated by polarization microscopy, electron probe microanalyses (EPMA), X-ray diffraction (XRD), and leaching tests as well as by hydrogeochemical modelling using LeachXSTM. Two samples showed elevated total contents of Cr, Ni, and Mo which were present as Cr-spinel, (Fe,Mg)(Al,Cr)2O4, Ni-olivine, (Fe,Mg,Ni)2SiO4, and molybdenite, MoS2. Whereas the former two phases also controlled the leaching of Cr and Ni, the observed leaching of Mo was higher than expected in the case of solubility control by molybdenite. In summary, the leachability of PEPE in natural and industrial aggregates was controlled by similar mineralogical mechanisms.