Methylobacterium strains were isolated from mangrove samples collected in Bertioga, SP, Brazil, from locations either contaminated or uncontaminated by oil spills. The tolerances of the strains to different heavy metals were assessed by exposing them to different concentrations of cadmium, lead, and arsenic (0.1mM, 0.5mM, 1mM, 2mM, 4mM, and 8mM). Additionally, the genetic diversity of Methylobacterium spp. was determined by sequence analysis of the 16S rRNA genes. The isolates from the contaminated locations were grouped, suggesting that oil can select for microorganisms that tolerate oil components and can change the methylotrophic bacterial community. Cadmium is the most toxic heavy metal assessed in this work, followed by arsenic and lead, and two isolates of Methylobacterium were found to be tolerant to all three metals. These isolates have the potential to bioremediate mangrove environments contaminated by oil spills by immobilizing the heavy metals present in the oil.