While there is increasing evidence for habitat specialization in coral reef fishes, the extent to which different corals support different fish communities is not well understood. Here we quantitatively assess the relative importance of different coral species in structuring fish communities and evaluate whether sampling scale and coral colony size affect the perceived strength of fish-habitat relationships. Fish communities present on colonies of eight coral species (Porites cylindrica, Echinopora horrida, Hydnophora rigida, Stylophora pistillata, Seriatopora hystrix, Acropora formosa, A. tenuis and A. millepora) were examined in the Lizard Island lagoon, Great Barrier Reef, Australia. Additionally, the differences in fish communities supported by three coral species (P. cylindrica, E. horrida, H. rigida) were investigated at three spatial scales of sampling (2x2 m, 1x1 m, 0.5x0.5 m). Substantial differences in fish communities were observed across the different coral species, with E. horrida and H. rigida supporting the most fish species and individuals. Coral species explained more of the variability in fish species richness (20.9–53.6%), than in fish abundance (0–15%). Most coral species supported distinctive fish communities, with dissimilarities ranging from 50 to 90%. For three focal coral species, a greater amount of total variation in fish species richness and fish abundance was evident at a larger scale of sampling. Together, these results indicate that the structure of reef fish communities is finely tuned to coral species. Loss of preferred coral species could have profound effects on reef fish biodiversity, potentially more so than would be predicted on the basis of declining coral cover alone.