Selenate is one of the most common toxic metal compounds in contaminated soils. Its redox status can be changed by microbial activity, thus affecting its water solubility and soil mobility. However, current knowledge of microbial dynamics has been limited by the low sensitivity of past isolation and identification protocols. Here, high-throughput Illumina sequencing of 16S rRNA genes was applied to monitor the shift of the microorganisms in an anoxic contaminated soil after Se(VI) and acetate amendment. An autoclaved soil with both chemicals and a live soil with acetate alone were used as controls. Preliminary chemical analysis clearly showed the occurrence of biological selenate reduction coupled with acetate oxidation. Principal coordinate analysis and diversity indices of Illumina-derived sequence data showed dynamic succession and diversification of the microbial community in response to selenate reduction. High-resolution phylogenetic analysis revealed that the relative frequency of an operational taxonomic unit (OTU) from the genus Dechloromonas increased remarkably from 0.2% to 36% as a result of Se(VI) addition. Multiple OTUs representing less abundant microorganisms from the Rhodocyclaceae and Comamonadaceae families had significant increases as well. This study demonstrated that these microorganisms are concertedly involved in selenate reduction of the employed contaminated soil under anoxic conditions.