The coralline sponge Astrosclera willeyana, considered to be a living representative of the reef-building stromatoporoids of the Mesozoic and the Paleozoic periods, occurs widely throughout the Indo-Pacific oceans. We aimed to examine, for the first time, the phylogenetic diversity of the microbial symbionts associated with A. willeyana using molecular methods and to investigate the spatial variability in the sponge-derived microbial communities of A. willeyana from diverse sites along the Great Barrier Reef (GBR). Both denaturing gradient gel electrophoresis (DGGE) analyses of 12 Astrosclera specimens and sequencing of a 16S rRNA gene clone library, constructed using a specimen of A. willeyana from the Yonge Reef (380 clones), revealed the presence of a complex microbial community with high diversity. An assessment of the 16S rRNA gene sequences to the particular phylogenetic groups showed domination of the Chloroflexi (42 %), followed by the Gammaproteobacteria (14 %), Actinobacteria (11 %), Acidobacteria (8 %), and the Deferribacteres (7 %). Of the microbes that were identified, a further 15 % belonged to the Deltaproteobacteria, Alphaproteobacteria, and Nitrospirae genera. The minor phylogenetic groups Gemmatimonadetes, Spirochaetes, Cyanobacteria, Poribacteria, and the Archaea composed 3 % of the community. Over 94 % of the sequences obtained from A. willeyana grouped together with other sponge- or coral-derived sequences, and of these, 72 % formed, with nearest relatives, 46 sponge-specific or sponge-coral clusters, highlighting the uniqueness of the microbial consortia in sponges. The DGGE results showed clear divisions according to the geographical origin of the samples, indicating closer relationships between the microbial communities with respect to their geographic origin (northern vs. southern GBR).