The recycling of scrap tire rubber requires high levels of energy, which poses challenges to its proper valorization. The application of rubber in construction requires significant mechanical and/or chemical treatment of scrap rubber to compatiblize it with the surrounding matrix. These methods are energy-consuming and costly and may lead to environmental concerns associated with chemical leachates. Furthermore, recent methods usually call for single-size rubber particles or a narrow rubber particle size distribution; this, in turn, adds to the pre-processing cost. Here, we used microbial etching (e.g., microbial metabolism) to modify the surface of rubber particles of varying sizes. Specifically, we subjected rubber particles with diameters of 1.18 mm and 0.6 mm to incubation in flask bioreactors containing a mineral medium with thiosulfate and acetate and inoculated them with a microbial culture from waste-activated sludge. The near-stoichiometric oxidation of thiosulfate to sulfate was observed in the bioreactors. Most notably, two of the most potent rubber-degrading bacteria (Gordonia and Nocardia) were found to be significantly enriched in the medium. In the absence of added thiosulfate in the medium, sulfate production, likely from the desulfurization of the rubber, was also observed. Microbial etching increased the surface polarity of rubber particles, enhancing their interactions with bitumen. This was evidenced by an 82% reduction in rubber–bitumen separation when 1.18 mm microbially etched rubber was used. The study outcomes provide supporting evidence for a rubber recycling method that is environmentally friendly and has a low cost, promoting pavement sustainability and resource conservation.