Before vaccination, Alaska Natives experienced very high rates of invasive Haemophilus influenzae type b (Hib) disease and carriage. Vaccination with Hib conjugate vaccine PRP-OMP (polyribosylribitol phosphate Neisseria meningitidis outer membrane protein) began in 1991 and resulted in a sharp decline in cases. In 1996, after switching to a different Hib conjugate vaccine, DTP-HbOC (which combines diphtheria-tetanus-whole cell pertussis vaccines with HbOC [Hib oligosaccharide CRM197]), cases of invasive Hib disease increased, suggesting ongoing Hib transmission despite widespread vaccination. To determine the prevalence of and risk factors for carriage, a cross-sectional study of oropharyngeal Hib carriage was conducted among Alaska Native children aged 1-5 years in remote southwestern Alaska. Of 496 children with swabs taken, 46 (9.3%) were colonized with Hib. Carriage rates varied by village from 2.2% to 13.2% and by age from 6.1% in 1-year-olds to 14.7% in 5-year-olds. Crowding was associated with Hib carriage. Widespread vaccination with PRP-OMP Hib conjugate vaccine did not eliminate carriage in this population of Alaska Natives, and ongoing carriage contributed to disease resurgence.