O -glycosylation is a post-translational modification of proteins crucial to molecular mechanisms in health and disease. O -glycans are typically highly heterogeneous. The involvement of specific O -glycan sequences in many bio-recognition systems is yet to be determined because of a lack of efficient methodologies. We describe here a targeted microarray approach: O -glycome beam search that is both robust and efficient for O -glycan ligand-discovery. Substantial simplification of the complex O -glycome profile and facile chromatographic resolution is achieved by arraying O -glycans as branches, monitoring by mass spectrometry, focusing on promising fractions, and on-array immuno-sequencing. This is orders of magnitude more sensitive than traditional methods. We have applied beam search approach to porcine stomach mucin and identified extremely minor components previously undetected within the O -glycome of this mucin that are ligands for the adhesive proteins of two rotaviruses. The approach is applicable to O -glycome recognition studies in a wide range of biological settings to give insights into glycan recognition structures in natural microenvironments.