Al Wajh Bank in the northern Red Sea contains an extensive coral reef system that potentially supports a novel fish community. The large (1500km2) and shallow (< 40m depth) lagoon experiences greater temperature and salinity fluctuations, as well as higher turbidity, than most other Red Sea reefs. Since these conditions often influence coral community structure and introduce physiological challenges to its resident organisms, changes in reef-associated fishes are expected. We present critical baseline data on fish biodiversity and benthic composition for the Al Wajh Bank. Underwater visual census of conspicuous fishes and standardized collections of cryptobenthic fishes were combined to provide a comprehensive assessment of these fish communities. We documented 153 fish species and operational taxonomic units, including undescribed species, within 24 families on reefs largely dominated by hard coral and soft sediment (39% and 32% respectively). The families Pomacentridae and Gobiidae contributed the most towards fish diversity and abundance. Bray-Curtis dissimilarity distances among sampled sites suggest a distinctive fish community within the lagoon, and coefficients of variation for each species show high variation in their distribution across the lagoon. Species accumulation curves predict that additional sampling would document many more species throughout Al Wajh. Our findings provide the most extensive biodiversity survey of fishes from this region to date and record the condition of the reef prior to major coastal development planned to occur in the near future.