Sponge diseases have been widely reported, yet the causal factors and major pathogenic microbes remain elusive. In this study, two individuals of the sponge Crella cyathophora in total that showed similar disease-like characteristics were collected from two different locations along the Red Sea coast separated by more than 30 kilometers. The disease-like parts of the two individuals were both covered by green surfaces, and the body size was much smaller compared with adjacent healthy regions. Here, using high-throughput pyrosequencing technology, we investigated the prokaryotic communities in healthy and disease-like sponge tissues as well as adjacent seawater. Microbes in healthy tissues belonged mainly to the Proteobacteria, Cyanobacteria and Bacteroidetes, and were much more diverse at the phylum level than reported previously. Interestingly, the disease-like tissues from the two sponge individuals underwent shifts of prokaryotic communities and were both enriched with a novel clade affiliated with the phylum Verrucomicrobia, implying its intimate connection with the disease-like Red Sea sponge C. cyathophora. Enrichment of the phylum Verrucomicrobia was also considered to be correlated with the presence of algae assemblages forming the green surface of the disease-like sponge tissues. This finding represents an interesting case of sponge disease and is valuable for further study.