Conservation and management of marine biodiversity depends on biomonitoring of marine habitats, but current approaches are resource-intensive and require different approaches for different organisms. Environmental DNA (eDNA) extracted from water samples is an efficient and versatile approach to detecting aquatic animals. In the ocean, eDNA composition reflects local fauna at fine spatial scales, but little is known about the effectiveness of eDNA-based monitoring of marine communities at larger scales. We investigated the potential of eDNA to characterize and distinguish marine communities at large spatial scales by comparing vertebrate species composition among marine habitats in Qatar, the Arabian Gulf (also known as the Persian Gulf), based on eDNA metabarcoding of seawater samples. We conducted species accumulation analyses to estimate how much of the vertebrate diversity we detected. We obtained eDNA sequences from a diverse assemblage of marine vertebrates, spanning 191 taxa in 73 families. These included rare and endangered species and covered 36% of the bony fish genera previously recorded in the Gulf. Sites of similar habitat type were also similar in eDNA composition. The species accumulation analyses showed that the number of sample replicates was insufficient for some sampling sites but suggested that a few hundred eDNA samples could potentially capture >90% of the marine vertebrate diversity in the study area. Our results confirm that seawater samples contain habitat-characteristic molecular signatures and that eDNA monitoring can efficiently cover vertebrate diversity at scales relevant to national and regional conservation and management.