Rezoning the Great Barrier Reef (GBR) Marine Park into no-take and take zones in 2004 demonstrated benefits in protected reefs including increased biomass of fish species targeted by fisheries, lower coral disease, less severe outbreaks of crown-of-thorns starfish, and faster recovery of coral communities to acute disturbances. Here, we investigated how seawater microbiomes are structured within no-take and take reefs in the GBR, using ~5,000 seawater bacterial and archaeal metagenome-assembled genomes (MAGs) collected from across the GBR. Integrative multivariate methods identified 160 indicator microbes that predict reef zoning with ~70% accuracy. Oligotrophic Pelagibacter and SAR86 MAGs with streamlined genomes were indicative of no-take zones, while opportunistic Flavobacteriaceae and Rhodobacteraceae were associated with take zones. Patterns in no-take zones were explained by increased crustose coralline algae, encrusting and tabulate Acropora, dissolved phosphorus, and herbivorous and detritivorous fish, while dissolved nitrogen and soft coral cover were elevated in take zones. A metric of microbial networks (‘cohesion’) identified competitive microbe-to-microbe interactions were prevalent in take zones, with indicator microbes of take zones outcompeting other microbes for dissolved nitrogen. These indicator microbes hold potential to assess health status of protected reefs, compliance with reef zoning, and future development of indices for fish stock assessments.