Using reclaimed asphalt pavement (RAP) material in pavement construction is typically an environmentally friendly practice. However, the asphalt available in RAP is already oxidized and stiffened due to various environmental processes. To compensate these problems, rejuvenators can be mixed with aged binder with the aim of restoring its original properties. This study investigates the performance of aged binders blended with three different types of rejuvenators. Thin-film oven test aged PG 58–28 binder was mixed with raw waste cooking oil (R1), modified waste cooking oil (R2), and Hydrolene H90T (R3) at the concentrations of 3%, 6% and 9% by the weight of the total binder. To enhance rutting resistance, styrene–butadiene–styrene was also blended with rejuvenated binders and tested. Frequency sweep testing at a wide range of temperatures and frequencies was conducted in the Dynamic Shear Rheometer, and time–temperature superposition was used to obtain parameters including Superpave, Glover-Rowe, Shenoy, Crossover frequency and Rheological index parameters. In addition, the Multi Stress Creep Recovery test was performed to gain an in-depth understanding of the rutting performance of the binders. Based on the comparative study of different rejuvenated binders, the binder rejuvenated using a chemically modified waste cooking oil seems to most be effective in improving the overall performance of the binder without compromising its rutting resistance. In addition, the relationship between different cracking parameters indicated that they are not all compatible with each other in terms of ranking binder performance. Finally, the MSCR parameter seems to more effectively capture the influence of rejuvenation and SBS addition to rejuvenated binders more than other parameters.