In contrast to the abundance of literature on the relationship between fish assemblages and habitat structure in the upper 30 m of coral reefs, the deeper (>40 m) parts of coral reefs are rarely studied. We examined changes in reef fish diversity and habitat structure along an increasing depth gradient, including the unknown deep reef. We ran visual and video transects along a substantial depth gradient (0 to 65 m) in the northern Red Sea and extended the known depth distribution for 48 reef species. We found a change in assemblage composition highly correlated to both the depth gradient and a reduction in the abundance of branching corals with depth. The number of reef fish species declined with depth and we also measured a high species turnover as measured by beta diversity (βt,βw) in the deep reef. This pattern is mainly due to the replacement of the abundant damselfishes in the shallow reef, which prey on zooplankton, by zooplanktivorous sea basses and wrasses in the deep reef. The steep reduction in branching corals, which most damselfishes use for cover, may be the main factor contributing to this change. We found a peak in species richness (alpha diversity) at 30 m, a peak in βwat 50 to 65 m, and peaks in βtat 30 to 50 m and 50 to 65 m. The 30 m depth stratum shows species of both shallow and deep assemblages generating a transition zone with characters of both deep and shallow habitats. The fish assemblage continues to change with depth, and future research will determine if there exists a depth threshold at which the assemblage will stabilize.