Biofilm formation by bacteria is one of the main causes of fouling in industrial cooling water systems. In many gram-negative bacteria, biofilm formation is regulated by N-acyl-homoserine lactone (AHL)-mediated quorum sensing. In this study, we isolated three AHL-degrading bacteria from cooling water systems and identified them as Sphingomonas ursincola. The draft genome sequence of S. ursincola A1 revealed the presence of an AHL-degrading gene homolog, designated qsdS. The qsdS region was also amplified by PCR from the genomes of the other two S. ursincola strains, SF1 and SF8. Escherichia coli DH5α harboring a QsdS-expressing plasmid showed high degradative activity against AHLs with short and 3-oxo-substituted acyl chains. High-performance liquid chromatography analysis revealed that QsdS is an AHL lactonase, an enzyme that catalyzes AHL ring opening. Furthermore, heterologous expression of QsdS in Pseudomonas aeruginosa PAO1 resulted in degradation of endogenous AHLs and interfered with the quorum-sensing-regulated phenotype.