End-of-life tires (ELTs) are among the most complex pollutants to treat due to their cross-linked structure resulting from the vulcanization process. Rubber biodesulfurization is a process used to treat or remove sulfur from rubber materials using microorganisms. This is considered a critical step for altering the cross-linked structure of vulcanized rubber and a subsequent more effective biodegradation or biotransformation treatment. The present study evaluated the desulfurizing capabilities of the strains Gordonia desulfuricans and Rhodococcus erythropolis on different elastomer mixtures of known composition and complex crumb rubber substrates. The results showed significant increases in sulfate concentration in cultures of R. erythropolis, mainly in the presence of butyl rubber and styrene butadiene rubber, achieving concentrations up to 181.9 ± 6.5 mg/L, 8-fold higher compared to controls. Both strains were able to alter the crosslinking density of the different rubber mixtures, reaching a maximum decrease of 26.7 %. An initial pretreatment was performed with Rhodococcus rhodochrous, and the treated crumb rubber samples were subsequently cultivated with the desulfurizing strains. Interestingly, a 2.5-fold higher sulfate concentration was achieved, and the crosslinking density was reduced to 16.3 % after culture with G. desulfuricans, decreasing from 453.4 mmol/L to 379.3 mmol/L. Thermogravimetric analyses confirm this additive effect by achieving a higher decrease in the maximum decomposition temperatures of the rubber samples. Thus, a two-stage bioprocess with greater effectiveness in terms of biodesulfurization is presented.