Background: Nontypeable Haemophilus influenzae (NTHi) colonize the human pharynx asymptomatically, and are an important cause of pediatric otitis media (OM). Previous research has identified genes more prevalent among OM-associated NTHi strains than among commensal strains, suggesting a role in virulence. However, these studies were unable to investigate the role of amino acid (aa) polymorphisms in virulence. Furthermore, there has been little work characterizing the population structure of NTHi. The research presented here investigated the diversity and population structure in a diverse collection of NTHi, and characterized OM-associated aa polymorphisms in the hemin receptor HemR. Methods: Multilocus sequence typing (MLST) was used to characterize 21 commensal isolates serially collected from two children. MLST was again performed on 170 commensal and OM NTHi isolates from Finland, Israel, and the US. The full hemR coding region was sequenced in 146 of the 170 isolates. The eBURST v3, ClonalFrame 1.1, and structure 2.3.3 programs were used to characterize diversity and population structure from the MLST data. HemR aa alignments were visually examined for polymorphisms, and R 2.13.0 was used to calculate odds ratios and p-values. HemR protein structure was modeled using I-TASSER. Results: MLST analysis of 21 isolates from two children found a high level of genetic diversity. Similar analysis of the collection of 170 isolates identified 109 unique sequence types (STs) and confirmed this diversity; little clustering was found by either disease or geography. Population structure was clearly evident, with support for eight populations when all 170 isolates were analyzed. Interestingly, one population contained only commensal isolates, while two others consisted solely of OM isolates. Fifteen HemR aa polymorphisms were significantly associated with OM. However, after adjusting for population structure only seven polymorphisms retained significance, demonstrating the confounding effect of population structure. The polymorphisms were found in a variety of structural and functional domains identified from the theoretical protein structure. Conclusions: NTHi is highly diverse, though population structure is still evident, and certain populations appear to be associated with OM. Seven HemR aa polymorphisms were associated with OM after adjustment for population structure, suggesting a role for this protein in virulence.