Initial cell attachment of rotavirus (RV) to specific cell surface glycan receptors, which is the essential first step in RV infection, is mediated by the VP8* domain of the spike protein VP4. Recently, human histo-blood group antigens (HBGAs) have been identified as receptors or attachment factors for human RV strains. RV strains in the P[4] and P[8] genotypes of the P[II] genogroup share common recognition of the Lewis b (Leb) and H type 1 antigens, however, the molecular basis of receptor recognition by the major human P[8] RVs remains unknown due to lack of experimental structural information. Here, we used nuclear magnetic resonance (NMR) spectroscopy-based titration experiments and NMR-derived high ambiguity driven docking (HADDOCK) methods to elucidate the molecular basis for P[8] VP8* recognition of the Leb (LNDFH I) and type 1 HBGAs. We also used X-ray crystallography to determine the molecular details underlying P[6] recognition of H type 1 HBGAs. Unlike P[6]/P[19] VP8*s that recognize H type 1 HBGAs in a binding surface composed of an α-helix and a β-sheet, referred as the "βα binding site", the P[8] and P[4] VP8*s bind Leb HBGAs in a previously undescribed pocket formed by the edges of two β-sheets, referred to as the "ββ binding site". Importantly, the P[8] and P[4] VP8*s retain binding capability to non-Leb type 1 HBGAs using the βα binding site. The presence of two distinct binding sites for Leb and non-Leb HBGA glycans in the P[8] and P[4] VP8* domains suggests host-pathogen co-evolution under structural and functional adaptation of RV pathogens to host glycan polymorphisms. Assessment and understanding of the precise impact of this co-evolutionary process in determining RV host ranges and cross-species RV transmission should facilitate improved RV vaccine development and prediction of future RV strain emergence and epidemics.