A culture-independent nested polymerase chain reaction (PCR) technique was used to investigate the diversity of actinobacteria communities associated with the sponges Hymeniacidon perleve and Sponge sp. The phylogenetic affiliation of sponge-derived actinobacteria was then assessed by 16S rRNA sequencing of cloned DNA fragments. A total of 196 positive clones were screened by restriction fragment length polymorphism (RFLP) analysis; 48 unique operational taxonomic units (OTUs) were selected for sequencing. Rarefaction analysis indicated that the clone libraries represented 93% and 94% of the total estimated diversity for the two species, respectively. Phylogenetic analysis of sequence data revealed representatives of various phylogenetic divisions, which were related to the following ten actinobacterial genera: Acidimicrobium, Corynebacterium, Propionibacterium, Actinomyces, Micrococcus, Microbacterium, Streptomyces, Mycobacterium, Cellulosimicrobium, Sporichthya, and unidentified actinobacterial clones. A sponge-specific, previously uncultured actinobacteria community grouped within the subclass Acidimicrobidae was discovered from both H. perleve and Sponge sp. Sequences belonging to Acidimicrobium in the H. perleve and the Sponge sp. clone libraries represented 33% and 24% of the clones, respectively. In the Sponge sp. clone library Mycobacterium dominated, accounting for 70% of all clones. The presence of Acidimicrobium and mycobacteria within two sponges can lay the groundwork for attempts to culture these interesting bacteria for industrial applications.