The reuse of waste materials in asphalt mixtures has been recently investigated, in order to develop new sustainable solutions for the road-paving industry. Such materials should improve the mechanical performance and provide safe/comfortable pavement surface courses for road users, without compromising their environmental performance. Thus, the aim of this study is to evaluate the mechanical, surface and environmental properties of stone mastic asphalt (SMA) mixtures produced with forward-looking asphalt binders incorporating waste materials. These binders were designed to maximise the waste material content using motor oil, high-density polyethylene, styrene–butadiene–styrene and crumb rubber, while performing so well as a commercial modified bitumen. Finally, the overall performance of the SMA mixtures produced with the selected binders was evaluated. It was concluded that these mixtures improve the water sensitivity, fatigue cracking and permanent deformation performance. The requirements for macrotexture, skid resistance and presence of heavy metals in leachates of these mixtures were similarly fulfilled. Thus, this work shows that new asphalt mixtures with waste materials can be used in road-paving works to improve the performance without compromising human and environmental safety.