Synthetic phytochelatins (ECs) composed of (Glu-Cys)nGly are protein analogs of phytochelatin that exhibit improved metal-binding capacity over metallothioneins (MTs). Expression of EC20 on the surface of E. coli using the Lpp-OmpA anchor resulted in improved bioaccumulation of cadmium and mercury, providing a new method for treating heavy metal contamination. To further improve the whole-cell accumulation of heavy metals, EC20 was expressed on the surface of Moraxella sp., a bacterium known to survive in contaminated environments, using the truncated ice nucleation protein (INPNC) anchor. Production of EC20 was approximately three-fold higher in Moraxella sp. than E. coli. As a consequence, the mercury-binding capacity of the recombinant Moraxella sp. was increased by more than 10-fold. Owing to the very high level of surface expression, the use of Moraxella sp. and INPNC anchor may prove to be useful for the remediation of other environmental contaminants.