Microhabitat-associated fishes are expected to be negatively affected by coral reef degradation, given that many species are coral dwellers. However, the factors underlying this negative impact and the spatial scale(s) at which it occurs are poorly understood. We explored how habitat quality metrics and host preferences influence fish abundance across multiple spatial scales, using the functionally important cleaner fish Elacatinus evelynae as a study species. We surveyed fish at 10 sites in Curaçao that varied in coral cover and health. At the microhabitat scale, we found that E. evelynae group size increases on large, healthy corals and on some coral host species, namely Montastraea cavernosa. We also found that, although E. evelynae can occupy at least 10 coral host species, it selectively inhabits just three corals: M. cavernosa, Colpophyllia natans, and Diploria labrynthiformis. Scaling up to explore goby abundance along 30-m transects, we did not find a clear relationship between live coral cover and goby abundance. However, goby abundance was substantially higher at one location with elevated coral cover and a high relative abundance of E. evelynae host species. Collectively, these results confirm that E. evelynae abundance is impacted by reef health. They also indicate that the species’ long-term persistence may depend on both the maintenance of healthy coral hosts and the gobies’ plasticity in host preferences on changing reefscapes. Cryptobenthic fishes such as E. evelynae play a vital role in the ecosystem and understanding drivers of their abundance is important as reefs face increased degradation.