Hydrocarbons from BTEX group are dangerous pollutants that can cause a threat to environment and human health. In many cases, their presence in an ecosystem is the result of accidents and petroleum products spills. For this reason, novel, more efficient sorbents are needed for immobilization of such pollutants. This paper presents an experimental study of recycled tires polymer fibers (RTPF) used as a low-cost sorbent for BTEX compounds in soils treated with cement. RTPF are a type of waste that contains polymer fibers with high content of rubber particles. The high porosity and large specific surface area of rubber result in possibility of use of RTPF as a removal material. Effectiveness of the application of RTPF as a BTEX removal material was evaluated on a basis of concentrations values above the surface of reacting mixture (at 25 ± 3 °C). It was found that RTPF addition increased BTEX immobilization efficacy, compared to the use of Portland cement alone. The maximum percentage reduction in BTEX compounds concentration was 33% for toluene. Lower level of removal was observed for ethylbenzene (21%), and substantially, small efficacy was noted for xylenes (8%) and benzene (7%). Additionally, in order to evaluate mechanical properties of soil–cement composites, analysis of their compressive strength after 28 days of maturation was performed. Tests showed a decrease in the compressive strength of soil–cement monoliths containing RTPF.