Estuarine sediments are significant repositories of anthropogenic contaminants, and thus knowledge of the impacts of pollution upon microbial communities in these environments is important to understand potential effects on estuaries as a whole. The Lagos lagoon (Nigeria) is one of Africa’s largest estuarine ecosystems, and is impacted by hydrocarbon pollutants and other industrial and municipal wastes. The goal of this study was to elucidate microbial community structure in Lagos lagoon sediments to identify groups that may be adversely affected by pollution, and those that may serve as degraders of environmental contaminants, especially polycyclic aromatic hydrocarbons (PAHs). Sediment samples were collected from sites that ranged in types and levels of anthropogenic impacts. The sediments were characterized for a range of physicochemical properties, and microbial community structure was determined by Illumina sequencing of the 16S rRNA genes. Microbial diversity (species richness and evenness) in the Apapa and Eledu sediments was reduced compared to that of the Ofin site, and communities of both of the former two were dominated by a single operational taxonomic unit (OTU) assigned to the family Helicobacteraceae (Epsilonproteobacteria). In the Ofin community, Epsilonproteobacteria were minor constituents, while the major groups were Cyanobacteria, Bacteroidetes, and Firmicutes, which were all minor in the Apapa and Eledu sediments. Sediment oxygen demand (SOD), a broad indicator of contamination, was identified by multivariate analyses as strongly correlated with variation in alpha diversity. Environmental variables that explained beta diversity patterns included SOD, as well as levels of naphthalene, acenaphthylene, cobalt, cadmium, total organic matter, or nitrate. Of 582 OTU identified, abundance of 167 was significantly correlated (false discovery rate q≤ 0.05) to environmental variables. The largest group of OTU correlated with PAH levels were PAH/hydrocarbon-degrading genera of the Oceanospirillales order (Gammaproteobacteria), which were most abundant in the hydrocarbon-contaminated Apapa sediment. Similar Oceanospirillales taxa are responsive to marine oil spills and thus may present a unifying theme in marine microbiology as bacteria adapted for degradation of high hydrocarbon loads, and may represent a potential means for intrinsic remediation in the case of the Lagos lagoon sediments.