Response of biological communities to environmental stresses is a critical issue in ecology, but how microbial communities shift across heavy metal gradients remain unclear. To explore the microbial response to heavy metal contamination (e.g., Cr, Mn, Zn), the composition, structure and functional potential of sedimentary microbial community were investigated by sequencing of 16S rRNA gene amplicons and a functional gene microarray. Analysis of 16S rRNA sequences revealed that the composition and structure of sedimentary microbial communities changed significantly across a gradient of heavy metal contamination, and the relative abundances were higher for Firmicutes, Chloroflexi and Crenarchaeota, but lower for Proteobacteria and Actinobacteria in highly contaminated samples. Also, molecular ecological network analysis of sequencing data indicated that their possible interactions might be enhanced in highly contaminated communities. Correspondently, key functional genes involved in metal homeostasis (e.g., chrR, metC, merB), carbon metabolism, and organic remediation showed a higher abundance in highly contaminated samples, indicating that bacterial communities in contaminated areas may modulate their energy consumption and organic remediation ability. This study indicated that the sedimentary indigenous microbial community may shift the composition and structure as well as function priority and interaction network to increase their adaptability and/or resistance to environmental contamination.