Submerged macrophytes play an important role in aquatic ecosystems, which has led to an increase in studies on vegetation recovery in polluted lakes from which submerged macrophytes have disappeared. The comparison of microbial communities in sediment cloned with planted and naturally growing submerged macrophytes is an interesting but rarely studied topic. In this investigation, Maojiabu and Xilihu, two adjacent sublakes of West Lake (Hangzhou, China), were selected as aquatic areas with planted and naturally growing macrophytes, respectively. Sediment samples from sites with/without Vallisneria natans were collected from both sublakes. The results showed that sediment total nitrogen and organic matter were significantly lower in the plant-covered sites than that in the non-plant sites in Maojiabu. Additionally, the sediment microbial community characterized by 16S ribosomal RNA (rRNA) sequencing differed more significantly for Maojiabu than for Xilihu. The relative abundances of microbes involved in C, N, and S elemental cycling were significantly higher in the sediments with plants than in those without. Results from both fatty acid methyl ester analysis and 16S rRNA sequencing indicated that vegetation significantly influenced the sulfate-reducing bacteria (SRB). Thus, the gene copies and composition of SRB were explored further. The relative gene abundance of SRB was 66% higher with natural vegetation colonization but was not influenced by artificial colonization. An increase in dominant SRB members from the families Syntrophobacteraceae and Thermodesulfovibrionaceae contributed to the increase of total SRB. Thus, macrophyte planting influences sediment nutrient levels and microbial community more than natural growth does, whereas the latter is more beneficial to sediment SRB.