Heavy metals (HMs) are compounds that can be hazardous and impair growth of living organisms. Bacteria have evolved the capability not only to cope with heavy metals but also to detoxify polluted environments. Three heavy metal-resistant strains of <i>Mucilaginibacer rubeus</i> and one of <i>Mucilaginibacter kameinonensis</i> were isolated from the gold/copper Zijin mining site, Longyan, Fujian, China. These strains were shown to exhibit high resistance to heavy metals with minimal inhibitory concentration reaching up to 3.5 mM Cu ^(II) , 21 mM Zn ^(II) , 1.2 mM Cd ^(II) , and 10.0 mM As ^(III) . Genomes of the four strains were sequenced by Illumina. Sequence analyses revealed the presence of a high abundance of heavy metal resistance (HMR) determinants. One of the strain, <i>M. rubeus</i> P2, carried genes encoding 6 putative P _IB-1 -ATPase, 5 putative P _IB-3 -ATPase, 4 putative Zn ^(II) /Cd ^(II) P _IB-4 type ATPase, and 16 putative resistance-nodulation-division (RND)-type metal transporter systems. Moreover, the four genomes contained a high abundance of genes coding for putative metal binding chaperones. Analysis of the close vicinity of these HMR determinants uncovered the presence of clusters of genes potentially associated with mobile genetic elements. These loci included genes coding for tyrosine recombinases (integrases) and subunits of mating pore (type 4 secretion system), respectively allowing integration/excision and conjugative transfer of numerous genomic islands. Further in silico analyses revealed that their genetic organization and gene products resemble the <i>Bacteroides</i> integrative and conjugative element CTnDOT. These results highlight the pivotal role of genomic islands in the acquisition and dissemination of adaptive traits, allowing for rapid adaption of bacteria and colonization of hostile environments.