Scleractinian corals harbor microorganisms that form dynamic associations with the coral host and exhibit substantial genetic and ecological diversity. Microbial associates may provide defense against pathogens and serve as bioindicators of changing environmental conditions. Here we describe the bacterial assemblages associated with two of the most common and phylogenetically divergent reef-building corals in the Caribbean, Montastraea faveolata and Porites astreoides. Contrasting life history strategies and disease susceptibilities indicate potential differences in their microbiota and immune function that may in part drive changes in the composition of coral reef communities. The ribotype structure and diversity of coral-associated bacteria within the surface mucosal layer (SML) of healthy corals were assessed using denaturing gradient gel electrophoresis (DGGE) fingerprinting and 454 bar-coded pyrosequencing. Corals were sampled at disparate Caribbean locations representing various levels of anthropogenic impact. We demonstrate here that M. faveolata and P. astreoides harbor distinct, host-specific bacteria but that specificity varies by species and site. P. astreoides generally hosts a bacterial assemblage of low diversity that is largely dominated by one bacterial genus, Endozoicomonas, within the order Oceanospirillales. The bacterial assemblages associated with M. faveolata are significantly more diverse and exhibit higher specificity at the family level than P. astreoides assemblages. Both corals have more bacterial diversity and higher abundances of disease-related bacteria at sites closer to the mainland than at those furthest away. The most diverse bacterial taxa and highest relative abundance of disease-associated bacteria were seen for corals near St. Thomas, U.S. Virgin Islands (USVI) (2.5 km from shore), and the least diverse taxa and lowest relative abundance were seen for corals near our most pristine site in Belize (20 km from shore). We conclude that the two coral species studied harbor distinct bacterial assemblages within the SML, but the degree to which each species maintains specific microbial associations varies both within each site and across large spatial scales. The taxonomic scale (i.e., phylum versus genus) at which scientists examine coral-microbe associations, in addition to host-elicited factors and environmental fluctuations, must be considered carefully in future studies of the coral holobiont.