To investigate the mechanism of cold adaptation of isocitrate lyase (ICL; EC 4.1.3.1) from the psychrophilic bacterium Colwellia maris, Gln207 and Gln217 of this enzyme were substituted by His and Lys, respectively, by site-directed mutagenesis. His184 and Lys194 of ICL from Escherichia coli, corresponding to the two Gln residues of C. maris ICL, are highly conserved in the ICLs of many organisms and are known to be essential for catalytic function. The mutated ICLs (Cm-Q207H and Cm-Q217K, respectively) and wild-type enzymes of C. maris and E. coli (Cm-WT and Ec-WT) with His-tagged peptides were overexpressed in E. coli cells and purified to homogeneity. Thermolabile Cm-WT and mutated ICLs were susceptible to digestion with trypsin, while relatively thermostable Ec-WT was resistant to trypsin digestion, suggesting that the thermostability and resistance to tryptic digestion of the ICLs are related. Cm-Q207H and Cm-Q217K showed specific activities similar to Cm-WT at temperatures between 30 °C and 40 °C, but their activities between 10 °C and 25 °C were decreased, indicating that the two Gln residues of the C. maris ICL play important roles in its cold adaptation. Phylogenetic analysis of ICLs from various organisms revealed that the C. maris ICL can be categorized in a novel group, subfamily 3, together with several eubacterial ICLs.