The hydrocracking of hydrotreated scrap tires pyrolysis oil (HT-STPO) has been studied aiming at high-quality refinery blends for alternative automotive fuels. The hydrocracking runs have been carried out with a PtPd/SiO2-Al2O3 catalyst in a fixed-bed reactor at 440–500 °C, 65 bar and space time of 0.16 h. The catalyst has been characterized by inductively coupled plasma optical emission spectroscopy, N2 adsorption–desorption isotherms, and tert-butylamine adsorption–desorption (TPD), while coke has been studied both quantitatively and qualitatively by thermogravimetric-temperature-programmed oxidation (TG-TPO), Fourier transform infrared-TPO, and Raman spectroscopy. During the first two hours of reaction and at temperatures above 480 °C, we have been able to (1) reach ultra low sulfur levels lower than 15 ppm; (2) remove almost completely the less interesting fraction—boiling points higher than 350 °C, named as the gasoil fraction—with remaining amounts lower than 1 wt %; (3) obtain a paraffinic and isoparaffinic content higher than 70 wt %. Catalyst deactivation is due to coke deposition having both an aromatic and aliphatic nature, while the aromaticity increases with process temperature. It has been proven that the temperature conditions can be tuned to reach a state in which coke is generated at the same rate that it is being hydrocracked.