A group of pigmented, psychrophilic, strictly aerobic chemoheterotrophs isolated from sea-ice cores collected from coastal areas of eastern Antarctica was found to represent a novel 16S rRNA lineage within the gamma subclass of the Proteobacteria, adjacent to the genus Alteromonas. The isolates are motile, Gram-negative, rod-shaped cells, which are psychrophilic and slightly halophilic, and possess an absolute requirement for seawater. Differences in phenotypic characteristics and DNA-DNA hybridization indicated the isolates formed two distinct taxa which have DNA G+C contents of 44-46 tool % and 40 mol%, respectively. Whole-cell fatty acid profiles of the isolates were however very similar and included 16: 1ω7c, 18: 1ω7c, 16:0 and 17: 1ω8c as the major fatty acid components. Overall, sufficient differences exist to distinguish the sea-ice strains from currently recognized bacterial genera. It is proposed the sea-ice strains represent a new genus, Glaciecola, which contains two species, Glaciecola punicea gen. nov., sp. nov. (ACAM 611(T)) and Glaciecola pallidula gen. nov., sp. nov. (ACAM 615(T)).