The new environmental targets set to save natural resources and recover waste materials have been the basis for several scientific studies in different research areas. Consequently, this work aims at developing recycled stone mastic asphalt mixtures with high rates of waste materials, including reclaimed asphalt pavements, waste engine oil products, waste polyethylene and crumb rubber. This new solution was compared with a conventional stone mastic asphalt mixture. Several blends of high penetration bitumens modified with waste materials and reclaimed aged bitumen were evaluated through basic and advanced tests, and the most promising solutions were selected to produce recycled stone mastic asphalt mixtures for further characterization. The water sensitivity, permanent deformation, and fatigue cracking performance of those mixtures incorporating high rates of different waste materials were generally improved. The exceptional behavior of these recycled mixtures together with the high incorporation rate of waste materials demonstrate the innovative character of these solutions for the road paving industry.