A culture-independent molecular phylogenetic approach was used to study prokaryotic diversity in an anoxic activated sludge from a municipal wastewater treatment plant. Two 16S rRNA gene libraries were constructed using total genomic DNA and amplified by polymerase chain reaction using primers specific for archaeal or bacterial domains. Phylogenetic analysis of 132 and 249 almost full-length 16S rRNA genes for Archaea and Bacteria, respectively, was done using the ARB software package. Phylogenetic groups affiliated with the Archaea belong to Euryarchaeota (93.8% of the operational taxonomic units [OTUs]) and Crenarchaeota (6.2% of the OTUs). Within the bacterial library, 84.8% of the OTUs represent novel putative phylotypes never described before and affiliated with ten divisions. The Proteobacteria phylum is the most abundant and diversified phylogenetic group representing 60.4% of the OTUs, followed by Bacteroidetes (22.1%) and gram-positives (6.1%). Interestingly, we detected a novel Proteobacteria monophyletic group distinct from the five known subclasses, which we named New Lineage of Proteobacteria (NLP) lineage, and it is composed of eight clones representing 4.6% of the Proteobacteria. A new 16S rRNA-targeted hybridization probe was designed and fluorescent in situ hybridization analyses shows representatives of NLP as cocci-shaped microorganisms. The Chloroflexi, Acidobacterium, and Nitrospira phyla and TM7 candidate division are each represented by ≤3% of clone sequences. A comprehensive set of eight 16S and 23S rRNA-targeted oligonucleotide probes was used to quantify these major groups by dot blot hybridization within 12 samples. The Proteobacteria accounted for 82.5 ± 4.9%, representing the most abundant phyla. The Bacteroidetes and Planctomycetales groups accounted for 4.9 ± 1.3% and 4 ± 1.7%, respectively. Firmicutes and Actinobacteria together accounted for only 1.9 ± 0.5%. The set of probes covers 93.4 ± 14% of the total bacterial population rRNA within the anoxic basin.