When Pseudomonas aeruginosa is grown with organosulfur compounds as sulfur sources, it synthesizes a set of proteins whose synthesis is repressed in the presence of sulfate, cysteine, or thiocyanate (so-called sulfate starvation-induced proteins). The gene encoding one of these proteins, PA13, was isolated from a cosmid library of P. aeruginosa PAO1 and sequenced. It encoded a 381-amino-acid protein that was related to several reduced flavin mononucleotide (FMNH2)-dependent monooxygenases, and it was the second in an operon of three genes, which we have named msuEDC. The MsuD protein catalyzed the desulfonation of alkanesulfonates, requiring oxygen and FMNH2 for the reaction, and showed highest activity with methanesulfonate. MsuE was an NADH-dependent flavin mononucleotide (FMN) reductase, which provided reduced FMN for the MsuD enzyme. Expression of the msu operon was analyzed with a transcriptional msuD::xylE fusion and was found to be repressed in the presence of sulfate, sulfite, sulfide, or cysteine and derepressed during growth with methionine or alkanesulfonates. Growth with methanesulfonate required an intact cysB gene, and the msu operon is therefore part of the cys regulon, since sulfite utilization was found to be CysB independent in this species. Measurements of msuD::xylE expression in cysN and cysI genetic backgrounds showed that sulfate, sulfite, and sulfide or cysteine play independent roles in negatively regulating msu expression, and sulfonate utilization therefore appears to be tightly regulated.