Background: Mesorhizobium metallidurans STM 2683(T) and Mesorhizobium sp. strain STM 4661 were isolated from nodules of the metallicolous legume Anthyllis vulneraria from distant mining spoils. They tolerate unusually high Zinc and Cadmium concentrations as compared to other mesorhizobia. This work aims to study the gene expression profiles associated with Zinc or Cadmium exposure and to identify genes involved in metal tolerance in these two metallicolous Mesorhizobium strains of interest for mine phytostabilization purposes. Results: The draft genomes of the two Mezorhizobium strains were sequenced and used to map RNAseq data obtained after Zinc or Cadmium stresses. Comparative genomics and transcriptomics allowed the rapid discovery of metal-specific or/and strain-specific genes. Respectively 1.05% (72/6,844) and 0.97% (68/6,994) predicted Coding DNA Sequences (CDS) for STM 2683 and STM 4661 were significantly differentially expressed upon metal exposure. Among these, a significant number of CDS involved in transport (13/72 and 13/68 for STM 2683 and STM 4661, respectively) and sequestration (15/72 and 16/68 for STM 2683 and STM 4661, respectively) were identified. Thirteen CDS presented homologs in both strains and were differentially regulated by Zinc and/or Cadmium. For instance, several PIB-type ATPases and genes likely to participate in metal sequestration were identified. Among the conserved CDS that showed differential regulation in the two isolates, we also found znuABC homologs encoding for a high affinity ABC-type Zinc import system probably involved in Zinc homeostasis. Additionally, global analyses suggested that both metals also repressed significantly the translational machinery. Conclusions: The comparative RNAseq-based approach revealed a relatively low number of genes significantly regulated in the two Mesorhizobium strains. Very few of them were involved in the non-specific metal response, indicating that the approach was well suited for identifying genes that specifically respond to Zinc and Cadmium. Among significantly up-regulated genes, several encode metal efflux and sequestration systems which can be considered as the most widely represented mechanisms of rhizobial metal tolerance. Downstream functional studies will increase successful phytostabilization strategies by selecting appropriate metallicolous rhizobial partners.