In this study, 454 pyrosequencing of the 16S rRNA gene was used to investigate sediment bacterial community response to contaminant disturbance across six estuaries with differing levels of 'modification'. We observed a significant influence of metal and polycyclic aromatic hydrocarbon contaminants in shaping bacterial community composition, structure and diversity, with metals being the more influential contaminant. An abundant and pervasive 'core' set of bacteria found in every sample were largely responsible for mediating community response to contamination. These 13 core operational taxonomic units were mostly comprised of Gamma-, Delta-, Alphaproteobacteria and Acidobacteria. Sediment silt and metals together explained the most variation in bacterial community composition (19.7%). Following this strong contaminant signature, salinity and temperature represented important environmental variables predicting 10.9% of community variation. While overall network connectivity measures supported the idea of an inherently diverse soil microbiome with some degree of functional redundancy, lower values observed in contaminated sediments indicate potential structural perturbations in the community from fracturing or loss of bacterial associations. The large number of unclassified sequences obtained in this study contribute to improving our understanding of environmentally relevant strains in relation to anthropogenic contamination, which have been overlooked in laboratory studies.