Modern strategies in radio-immuno therapy and in vivo imaging require robust, small, and specific ligand-binding proteins. In this context we have previously developed artificial lipocalins, so-called Anticalins, with high binding activity toward rare-earth metal–chelate complexes using combinatorial protein design. Here we describe further improvement of the Anticalin C26 via in vitro affinity maturation to yield CL31, which has a fourfold slower dissociation half-life above 2 h. Also, we present the crystallographic analyses of both the initial and the improved Anticalin, providing insight into the molecular mechanism of chelated metal binding and the role of amino acid substitutions during the step-wise affinity maturation. Notably, one of the four structurally variable loops that form the ligand pocket in the lipocalin scaffold undergoes a significant conformational change from C26 to CL31, acting as a lid that closes over the accommodated metal–chelate ligand. A systematic mutational study indicated that further improvement of ligand affinity is difficult to achieve while providing clues on the contribution of relevant side chains in the engineered binding pocket. Unexpectedly, some of the amino acid replacements led to strong increases – more then 10-fold – in the yield of soluble protein from periplasmic secretion in Escherichia coli.