Rice paddy soil has been shown to have strong denitrifying activity. However, the microbial populations responsible for nitrate respiration and denitrification have not been well characterized. In this study, we performed a clone library analysis of >1,000 clones of the nearly full-length 16S rRNA gene to characterize bacterial community structure in rice paddy soil. We also identified potential key players in nitrate respiration and denitrification by comparing the community structures of soils with strong denitrifying activity to those of soils without denitrifying activity. Clone library analysis showed that bacteria belonging to the phylum Firmicutes, including a unique Symbiobacterium clade, dominated the clones obtained in this study. Using the template match method, several operational taxonomic units (OTUs), most belonging to the orders Burkholderiales and Rhodocyclales, were identified as OTUs that were specifically enriched in the sample with strong denitrifying activity. Almost one-half of these OTUs were classified in the genus Herbaspirillum and appeared >10-fold more frequently in the soils with strong denitrifying activity than in the soils without denitrifying activity. Therefore, OTUs related to Herbaspirillum are potential key players in nitrate respiration and denitrification under the conditions used.