The crystal structure of a cold-active aminopeptidase (ColAP) from Colwellia psychrerythraea strain 34H has been determined, extending the number of crystal structures of the M1 metallopeptidase family to four among the 436 members currently identified. In agreement with their sequence similarity, the overall structure of ColAP displayed a high correspondence with leukotriene A4 hydrolase (LTA4H), a human bifunctional enzyme that converts leukotriene A4 (LTA4) in the potent chemoattractant leukotriene B4. Indeed, both enzymes are composed of three domains, an N-terminal saddle-like domain, a catalytic thermolysin-like domain, and a less conserved C-terminal alpha-helical flat spiral domain. Together, these domains form a deep cavity harboring the zinc binding site formed by residues included in the conserved HEXXHX(18)H motif. A detailed structural comparison of these enzymes revealed several plausible determinants of ColAP cold adaptation. The main differences involve specific amino acid substitutions, loop content and solvent exposure, complexity and distribution of ion pairs, and differential domain flexibilities. Such elements may act synergistically to allow conformational flexibility needed for an efficient catalysis in cold environments. Furthermore, the region of ColAP corresponding to the aminopeptidase active site of LTA4H is much more conserved than the suggested LTA4 substrate binding region. This observation supports the hypothesis that this region of the LTA4H active site has evolved in order to fit the lipidic substrate.