Hydrolysis of organic sulfate esters proceeds by two distinct mechanisms, water attacking at either sulfur (S-O bond cleavage) or carbon (C-O bond cleavage). In primary and secondary alkyl sulfates, attack at carbon is favored, whereas in aromatic sulfates and sulfated sugars, attack at sulfur is preferred. This mechanistic distinction is mirrored in the classification of enzymes that catalyze sulfate ester hydrolysis: arylsulfatases (ASs) catalyze S-O cleavage in sulfate sugars and arylsulfates, and alkyl sulfatases break the C-O bond of alkyl sulfates. Sinorhizobium meliloti choline sulfatase (SmCS) efficiently catalyzes the hydrolysis of alkyl sulfate choline-O-sulfate (kcat/KM=4.8×103s-1M-1) as well as arylsulfate 4-nitrophenyl sulfate (kcat/KM=12s-1M-1). Its 2.8-Å resolution X-ray structure shows a buried, largely hydrophobic active site in which a conserved glutamate (Glu386) plays a role in recognition of the quaternary ammonium group of the choline substrate. SmCS structurally resembles members of the alkaline phosphatase superfamily, being most closely related to dimeric ASs and tetrameric phosphonate monoester hydrolases. Although >70% of the amino acids between protomers align structurally (RMSDs 1.79-1.99Å), the oligomeric structures show distinctly different packing and protomer-protomer interfaces. The latter also play an important role in active site formation. Mutagenesis of the conserved active site residues typical for ASs, H218O-labeling studies and the observation of catalytically promiscuous behavior toward phosphoesters confirm the close relation to alkaline phosphatase superfamily members and suggest that SmCS is an AS that catalyzes S-O cleavage in alkyl sulfate esters with extreme catalytic proficiency.