We investigated microorganisms associated with a deep-sea sponge, Characella sp. (Pachastrellidae) collected at a hydrothermal vent site (686 m depth) in the Sumisu Caldera, Ogasawara Island chain, Japan, and with two sponges, Pachastrella sp. (Pachastrellidae) and an unidentified Poecilosclerida sponge, collected at an oil seep (572 m depth) in the Gulf of Mexico, using polymerase chain reaction-denaturing gradient gel electrophoresis (PCR-DGGE) directed at bacterial 16S rRNA gene sequences. In the PCR-DGGE profiles, we detected a single clearly dominant band in each of the Characella sp. and the unidentified Poecilosclerida sponge. BLAST search of their sequences showed that they were most similar (>99% identity) to those of the gammaproteobacterial thioautotrophic symbionts of deep-sea bivalves from hydrothermal vents, Bathymodiolus spp. Phylogenetic analysis of the near-full length sequences of the 16S rRNA genes cloned from the unidentified Poecilosclerida sponge and Characella sp. confirmed that they were closely related to thioautotrophic symbionts. Although associations between sponges and methanotrophic bacteria have been reported previously, this is the first report of a possible stable association between sponges and thioautotrophic bacteria.