Microbes associated with marine sponges play significant roles in host physiology. Remarkable levels of microbial diversity have been observed in sponges worldwide through both culture-dependent and culture-independent studies. Most studies have focused on the structure of the bacterial communities in sponges and have involved sponges sampled from shallow waters. Here, we used pyrosequencing of 16S rRNA genes to compare the bacterial and archaeal communities associated with two individuals of the marine sponge Inflatella pellicula from the deep-sea, sampled from a depth of 2,900 m, a depth which far exceeds any previous sequence-based report of sponge-associated microbial communities. Sponge-microbial communities were also compared to the microbial community in the surrounding seawater. Sponge-associated microbial communities were dominated by archaeal sequencing reads with a single archaeal OTU, comprising ~60% and ~72% of sequences, being observed from Inflatella pellicula. Archaeal sequencing reads were less abundant in seawater (~11% of sequences). Sponge-associated microbial communities were less diverse and less even than any other sponge-microbial community investigated to date with just 210 and 273 OTUs (97% sequence identity) identified in sponges, with 4 and 6 dominant OTUs comprising ~88% and ~89% of sequences, respectively. Members of the candidate phyla, SAR406, NC10 and ZB3 are reported here from sponges for the first time, increasing the number of bacterial phyla or candidate divisions associated with sponges to 43. A minor cohort from both sponge samples (~0.2% and ~0.3% of sequences) were not classified to phylum level. A single OTU, common to both sponge individuals, dominates these unclassified reads and shares sequence homology with a sponge associated clone which itself has no known close relative and may represent a novel taxon.