The plant growth-promoting effect of Pseudomonas putida S-313 is associated with its ability to desulfurize arylsulfonates. To understand this further, other plant-associated bacteria able to desulfurize a range of arylsulfonates were isolated from the rhizospheres of winter and spring barley. The isolates belonged to the beta-proteobacteria, including bacteria from the Variovorax paradoxus group and from the Acidovorax genus. They desulfurized toluenesulfonate to p-cresol, and were found to contain orthologues of the P. putida S-313 asfA gene (> 70% sequence identity to AsfA), which is required for aryldesulfonation in this species. Further putative asfA orthologues were identified in several bacteria and cyanobacteria whose genomes have been sequenced, but of these only Cupriavidus (Ralstonia) metallidurans was able to utilize arylsulfonates as sulfur source. Cultivation of V. paradoxus, C. metallidurans or P. putida S-313 with toluenesulfonate as sulfur source led to a 100-fold increase in expression of the asfA homologues, which was largely repressed when sulfate was added. Polymerase chain reaction with degenerate primers was used to generate asfAB clone libraries from spring- and winter-barley rhizosphere DNA. Cluster analysis of 76 sequenced AsfA fragments revealed a broad diversity, with the majority of the sequences clustered together with AsfA from bacteria that are able to utilize toluenesulfonate as sulfur source. The diversity of asfA in barley rhizosphere underlines the importance of the desulfonation process for bacteria that inhabit the plant rhizosphere.