We have determined the crystal structure of YodA, an Escherichia coli protein of unknown function. YodA had been identified under conditions of cadmium stress, and we confirm that it binds metals such as cadmium and zinc. We have also found nickel bound in one of the crystal forms. YodA is composed of two domains: a main lipocalin/calycin-like domain and a helical domain. The principal metal-binding site lies on one side of the calycin domain, thus making YodA the first metal-binding lipocalin known. Our experiments suggest that YodA expression may be part of a more general stress response. From sequence analogy with the C-terminal domain of a metal-binding receptor of a member of bacterial ATP-binding cassette transporters, we propose a three-dimensional model for this receptor and suggest that YodA may have a receptor-type partner in E. coli.