The environmental concern about waste generation and the gradual decrease of oil reserves has led the way to finding new waste materials that may partially replace the bitumens used in the road paving industry. Used motor oil from vehicles is a waste product that could answer that demand, but it can also drastically reduce the viscosity, increasing the asphalt mixture’s rutting potential. Therefore, polymer modification should be used in order to avoid compromising the required performance of asphalt mixtures when higher amounts of waste motor oil are used. Thus, this study was aimed at assessing the performance of an asphalt binder/mixture obtained by replacing part of a paving grade bitumen (35/50) with 10% waste motor oil and 5% styrene-butadiene-styrene (SBS) as an elastomer modifier. A comparison was also made with the results of a previous study using a blend of bio-oil from fast pyrolysis and ground tire rubber modifier as a partial substitute for usual PG64-22 bitumen. The asphalt binders were tested by means of Fourier infrared spectra and dynamic shear rheology, namely by assessing their continuous high-performance grade. Later, the water sensitivity, fatigue cracking resistance, dynamic modulus and rut resistance performance of the resulting asphalt mixtures was evaluated. It was concluded that the new binder studied in this work improves the asphalt mixture’s performance, making it an excellent solution for paving works.