A bacterial strain capable of hydrolyzing sulfate ester bonds in p-nitrophenyl sulfate and agar was isolated from the Southeast coast of Korea. The isolated strain (AS6330) is aerobic, Gram-negative, rod-shaped, and motile. Octadecanoic acid was the major cellular fatty acid in the isolate. An almost complete 16S rDNA sequence of the isolate was determined and the sequence similarity of the 16S rDNA with those of known Sphingomonas spp. was found to be at most $96.4\%$, implying that the isolate was a new Sphingomonas species. The organism was grown optimally at NaCl concentration of $1.5-3.5\%$. Optimum culture conditions were determined to be $30^{circ}C$ and pH 7.0 for 48 h fermentation using a laboratory fermentor under constant culture conditions. Partially purified arylsulfatase through Q-Sepharose and phenyl­Sepharose chromatographies catalyzed hydrolysis of sulfate ester bonds in agar, and $97\%$ of sulfates in agar were removed after 4 h reaction at $45^{circ}C$ and pH 7.0. The arylsulfatase from the isolated bacterium might be useful for the removal of sulfate groups in agar.