Rhizobium leguminosarum bv. viciae strains expressing different degrees of tolerance to metal stress were used in this work to study the basic mechanisms underlying heavy metal tolerance. We used various parameters to evaluate this response. The strains' growth responses under different Cd2+ concentrations were determined and we reported variation in Cd2+ tolerance. Total soluble protein content decreased drastically, revealing the toxic effects that intracellular Cd2+ imposes on cellular metabolism, but this decrease in protein content was particularly evident in sensitive and moderately tolerant strains. Tolerant strains presented the highest intracellular and wall-bound Cd2+ concentrations. Cd2+ induced increases in the expression of some specific proteins, which were identical in all tolerant strains. Glutathione levels remained unaltered in the sensitive strain and increased significantly in tolerant and moderately tolerant strains, suggesting the importance of glutathione in coping with metal stress. This work suggests that efflux mechanisms may not be the only system responsible for dealing with heavy metal tolerance. A clear correlation between glutathione levels and Cd2+ tolerance is reported, thus adding a novel aspect in bacteria protection against heavy metal deleterious effects.