Background Cold adapted or psychrophilic organisms grow at low temperatures, where most of other organisms cannot grow. This adaptation requires a vast array of sequence, structural and physiological adjustments. To understand the molecular basis of cold adaptation of proteins, we analyzed proteomes of psychrophilic and mesophilic bacterial species and compared the differences in amino acid composition and substitution patterns to investigate their likely association with growth temperatures. Results In psychrophilic bacteria, serine, aspartic acid, threonine and alanine are overrepresented in the coil regions of secondary structures, whilst glutamic acid and leucine are underrepresented in the helical regions. Compared to mesophiles, psychrophiles comprise a significantly higher proportion of amino acids that contribute to higher protein flexibility in the coil regions of proteins, such as those with tiny/small or neutral side chains. Amino acids with aliphatic, basic, aromatic and hydrophilic side chains are underrepresented in the helical regions of proteins of psychrophiles. The patterns of amino acid substitutions between the orthologous proteins of psychrophiles versus mesophiles are significantly different for several amino acids when compared to their substitutions in orthologous proteins of within the mesophiles or psychrophiles. Conclusion Current results provide quantitative substitution preferences (or avoidance) of amino acids that lead to the adaptation of proteins to cold temperatures. These finding would help future efforts in selecting mutations for rational design of proteins with enhanced psychrophilic properties.