Biodegradation of anionic surfactants, like sodium dodecyl sulfate (SDS) are challenged by some bacteria through the function of the enzyme alkyl sulfatases. Therefore, identifying and characterizing bacteria capable of degrading SDS with high alkyl sulfatase enzyme activity are pivotal. In this study, bacteria isolated from surfactant contaminated river water were screened for their potential to degrade SDS. Primary screening carried out by the conventional enrichment culture technique and assessment of SDS-degrading ability through methylene blue active substance assay revealed 12, out of 290, SDS-degrading surface water bacteria with maximum SDS degrading abilities of 46–94% in 24–54 h. The isolates exhibited optimum growth at SDS concentration of 1 g/L, but tolerated up to 15–75 g/L. Eleven isolates were identified as the species of Pseudomonas and one isolate was identified as Aeromonas through 16S rRNA sequencing. Proteolytic activity of alkyl sulfatases in the identified isolates was shown by using native-PAGE analysis. The determined enzyme activities changed in between 1.32 and 2.90 U/mg in the crude extracts. Preliminary experiments showed that the isolates with the alkyl sulfatase enzyme activities ≥2.50 U/mg were strong gratuitous degraders. However, their relative importance in soil, sewage, and wastewater treatment plants remains to be assessed.