In Mediterranean subtidal rocky reefs, Cystoseira spp. (Phaeophyceae) form dense canopies up to 1 m high. Such habitats, called ‘Cystoseira forests’, are regressing across the entire Mediterranean Sea due to multiple anthropogenic stressors, as are other large brown algae forests worldwide. Cystoseira forests are being replaced by structurally less complex habitats, but little information is available regarding the potential difference in the structure and composition of fish assemblages between these habitats. To fill this void, we compared necto-benthic (NB) and crypto-benthic (CB) fish assemblage structures between Cystoseira forests and two habitats usually replacing the forests (turf and barren), in two sampling regions (Corsica and Menorca). We sampled NB fish using Underwater Visual Census (UVC) and CB fish using Enclosed Anaesthetic Station Vacuuming (EASV), since UVC is known to underestimate the diversity and density of the ‘hard to spot’ CB fish. We found that both taxonomic diversity and total density of NB and CB fish were highest in Cystoseira forests and lowest in barrens, while turfs, that could be sampled only at Menorca, showed intermediate values. Conversely, total biomass of NB and CB fish did not differ between habitats because the larger average size of fish in barrens (and turfs) compensated for their lower densities. The NB families Labridae and Serranidae, and the CB families Blenniidae, Cliniidae, Gobiidae, Trypterigiidae and Scorpaenidae, were more abundant in forests. The NB taxa Diplodus spp. and Thalassoma pavo were more abundant in barrens. Our study highlights the importance of using EASV for sampling CB fish, and shows that Cystoseira forests support rich and diversified fish assemblages. This evidence suggests that the ongoing loss of Cystoseira forests may impair coastal fish assemblages and related goods and services to humans, and stresses the need to implement strategies for the successful conservation and/or recovery of marine forests.