Sodium dodecyl sulfate-polyacrylamide gel electrophoresis (SDS-PAGE) is a widely used technique for protein separation, and in-gel tryptic digestion of resolved protein bands has enhanced the resolution of protoeomic analysis. To augment this technology and expand its usefulness for glycoproteomics, we have developed and improved methods to release and recover O-linked glycans from proteins resolved in SDS-PAGE gels for subsequent analysis by mass spectrometry (MS). Gel pieces containing target proteins are washed to remove contaminants. O-linked glycans are released through reductive β-elimination by hydrating gel pieces in base and adding reductant. Following straightforward sample cleanup, this simple treatment of glycoprotein gel pieces produces material suitable for MS analysis. We have applied this method to the analysis of mucin-type glycoproteins that are expected to carry high densities of sialylated and sulfated O-linked glycans. However, the strongly acidic nature of the sulfate moiety suppresses MS signal intensities, hampering detection and quantitative analysis. To enhance detection, we present an improved method for sulfoglycomics. A mixture of sulflo-, sialo-, and neutral glycans were permethylated and partitioned into a water–dichloromethane (DCM) solvent mixture. Sulfated glycans were selectively recovered from the aqueous phase, while neutral and sialylated glycans remained in the DCM phase. When applied to the analysis of human mucin salivary glycans, this partition method generated material of sufficient quality to identify more than 60 glycan structures by NSI-MS (LTQ-Orbitrap) in positive and negative ion modes. Also, nearly 100% of the sulfated O-linked glycans were recovered in the aqueous phase, demonstrating the feasibility of in-depth sulfoglycomic analysis using SDS-PAGE resolved proteins.