A variety of stressors are causing long-term declines in coral cover on coral reefs, which is having significant impacts on reef fish biodiversity and community structure. Declining coral cover is often associated with increases in other benthic organisms, including macroalgae, encrusting ascidians and sponges. Here we combine observational and experimental approaches to test whether overgrowth of corals by encrusting sponges is impacting fish assemblages by reducing coral cover and substratum complexity. Firstly, fish assemblages were compared for 3x3m quadrats with low (<1%), medium (5-10%) and high (>20%) sponge cover. Secondly, fish responses to the experimental removal of sponges from high (>20%) sponge cover quadrats were quantified. Sponge cover had a significant negative effect on the fish assemblages, with high sponge cover quadrats having 44% less individuals and ~35% less fish species than quadrats with low sponge cover. These differences were not explained by reduced substratum complexity. High sponge cover plots also supported distinct assemblages, including high numbers of Ctenochaetus tominiensis, Neoglyphydodon nigroris, Lutjanus biguttatus and Amblyglyphidodon curacao. Areas with low and medium sponge cover were characterized by smaller cryptobenthic and coral-associated species. Experimental removal of encrusting sponges showed no effect on abundance or species richness of fishes after 100 days, with a temporal increase in these metrics in both sponge removals and controls. However, removal and control quadrats exhibited pronounced differences in assemblage structure by ~7 days after the removal, with 42 (38%) species detected exclusively in high sponge cover quadrats and 18 (~21%) only found on sponge removed quadrats. Numerous species (e.g., Eviota partimaculata, Atrosalarias fuscus, Pseudocheilinus ataenia, Neoglyphydodon nigroris, Lutjanus biguttatus) were abundant on high sponge cover quadrats, while many substratum associated species (e.g. Ecsenius bathi, Chromis retrofasciata, Archamia zosterophora, Thalassoma lunare, Labropsis australis and Halichoeres purpurecens) were more frequently found in sponge removal quadrats. The results indicate that encrusting sponges, even at as much as 40% cover, are having a substantial impact on local fish assemblages, with the differences among the observational and experimental results likely indicative of both long-term and short-term effects