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 due to 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.