Metals bound to proteins play key roles in structure stabilization, catalysis, and metal transport in cells, but metals may also be toxic. As a consequence, cells have developed mechanisms to control metal concentrations through binding to proteins. We have used a hyphenated strategy linking gel electrophoresis with laser ablation-inductively coupled plasma-mass spectrometry in order to detect, map, and quantify metal-binding proteins synthesized in Escherichia coli under zinc- and cadmium-stress conditions. We report the development of a powerful analytical method suitable for detection and characterization of metalloproteins in complex, unfractionated bacterial cell extracts. The approach was validated by using an E. coli strain overexpressing the cyanobacterial metallothionein protein SmtA. We observed induction of SmtA synthesis by zinc and binding of both zinc and cadmium cations by this protein. A profile of zinc- and cadmium-binding proteins was obtained from E. coli cytoplasmic fractions. Analysis of induction patterns and metal contents demonstrated the presence of proteins with high metal content which, on further study, should lead to the identification of novel metal-binding proteins.