Environmental protection is also pursued by promoting the saving of oil reserves and the proper management of waste through a circular economy. Following this objective, the present study encourages the use of recycled and by-product materials for the production of bituminous binders. The powdered rubber (R) from end-of-life tyres and the re-refined engine oil bottom (REOB), i.e. the by-product of refining mineral waste oils, were used to replace a certain amount of standard bitumen. The experimental program aims to characterize the interaction between R and REOB in order to use them as virgin bitumen extenders. The multiple variables of the production process that may affect the R-REOB blends and in turn the binders’ final properties were evaluated. The R-REOB mixes were prepared by varying the type of REOB, the R content and the mixing temperature. The rheological analysis was performed by means of dynamic shear rheometer (DSR) tests with the aim to define the variables that strongly influence the response of the R-REOB compound. As a result of this preliminary study, the second phase will focus on extended bitumens that will be prepared considering some of the studied extenders.