The low temperatures of polar regions and high-altitude environments, especially icy habitats, present challenges for many microorganisms. Their ability to live under subfreezing conditions implies the production of compounds conferring cryotolerance. Colwellia psychrerythraea 34H, a γ-proteobacterium isolated from subzero Arctic marine sediments, provides a model for the study of life in cold environments. We report here the identification and detailed molecular primary and secondary structures of capsular polysaccharide from C. psychrerythraea 34H cells. The polymer was isolated in the water layer when cells were extracted by phenol/water and characterized by one- and two-dimensional NMR spectroscopy together with chemical analysis. Molecular mechanics and dynamics calculations were also performed. The polysaccharide consists of a tetrasaccharidic repeating unit containing two amino sugars and two uronic acids bearing threonine as substituent. The structural features of this unique polysaccharide resemble those present in antifreeze proteins and glycoproteins. These results suggest a possible correlation between the capsule structure and the ability of C. psychrerythraea to colonize subfreezing marine environments.