While cold-adapted bacteria isolated from marine or terrestrial low temperature environments share many similarities, cold-adapted bacteria from terrestrial environments usually grow over a broader range of temperatures suggesting different constraints of these two low temperature environments. The diversity of habitats from which Psychrobacter have been isolated (e.g. cold marine environments, frozen soils, permafrost and humans) provides a unique opportunity to examine habitat specific adaptations while reducing phylogenetic effects. Here, comparative genomic analyses of 26 strains of Psychrobacter revealed several clusters with characteristics that correlated with habitat. Marine and terrestrial Psychrobacter have amino acid composition typical of psychrophiles (e.g. fewer proline and lysine, more acidic) when compared to Psychrobacter strains associated with warm hosts, and have many potentially cold-adapted core genes (e.g. ClpX, DsbC, GroEL/GroES and MutS2). Marine and terrestrial Psychrobacter share many genes (e.g. FadB) not found in warm host Psychrobacter, which had their own distinct gene content (e.g. collagenase-like protease). Furthermore, terrestrial Psychrobacter were differentiated from marine Psychrobacter by the use of different cold adaptations and more hydrophobic and aliphatic proteins. These data suggest that terrestrial and marine Psychrobacter evolved from a mesophilic ancestor and are accumulating adaptations for low temperatures as well as for their respective habitats.