Coral reefs harbor diverse assemblages of organisms yet the majority of this diversity is hidden within the three dimensional structure of the reef and neglected using standard visual surveys. This study uses Autonomous Reef Monitoring Structures (ARMS) and amplicon sequencing methodologies, targeting mitochondrial cytochrome oxidase I and 18S rRNA genes, to investigate changes in the cryptic reef biodiversity. ARMS, deployed at 11 sites across a near- to off-shore gradient in the Red Sea were dominated by Porifera (sessile fraction), Arthropoda and Annelida (mobile fractions). The two primer sets detected different taxa lists, but patterns in community composition and structure were similar. While the microhabitat of the ARMS deployment affected the community structure, a clear cross-shelf gradient was observed for all fractions investigated. The partitioning of beta-diversity revealed that replacement (i.e. the substitution of species) made the highest contribution with richness playing a smaller role. Hence, different reef habitats across the shelf are relevant to regional diversity, as they harbor different communities, a result with clear implications for the design of Marine Protected Areas. ARMS can be vital tools to assess biodiversity patterns in the generally neglected but species-rich cryptic benthos, providing invaluable information for the management and conservation of hard-bottomed habitats over local and global scales.