Toxic metals (such as lead, cadmium, and, to a lesser extent, aluminum) are detrimental to health when ingested in food or water or when inhaled. By interacting with heavy metals, gut and food-derived microbes can actively and/or passively modulate (by adsorption and/or sequestration) the bioavailability of these toxins inside the gut. This “intestinal bioremediation” involves the selection of safe microbes specifically able to immobilize metals. We used inductively coupled plasma mass spectrometry to investigate the in vitro ability of 225 bacteria to remove the potentially harmful trace elements lead, cadmium, and aluminum. Interspecies and intraspecies comparisons were performed among the Firmicutes (mostly lactic acid bacteria, including Lactobacillus spp., with some Lactococcus, Pediococcus, and Carnobacterium representatives), Actinobacteria, and Proteobacteria. The removal of a mixture of lead and cadmium was also investigated. Although the objective of the study was not to elucidate the mechanisms of heavy metal removal for each strain and each metal, we nevertheless identified promising candidate bacteria as probiotics for the intestinal bioremediation of Pb(II) and Cd(II).