Alginates are abundant polysaccharides in brown algae that constitute an important energy source for marine heterotrophic bacteria. Despite the key role of alginate degradation processes in the marine carbon cycle, little information is available on the bacterial populations involved in these processes. The aim of this work was to gain a better understanding of alginate utilization capabilities in cold coastal environments. Sediment metagenomes from four high-latitude regions of both Hemispheres were interrogated for alginate lyase gene homologue sequences and their genomic context. Sediments contained highly abundant and diverse bacterial assemblages with alginolytic potential, including members of Bacteroidetes and Proteobacteria, as well as several poorly characterized taxa. The microbial communities in Arctic and Antarctic sediments exhibited the most similar alginolytic profiles, whereas brackish sediments showed distinct structures with a higher proportion of novel genes. Examination of the gene neighbourhood of the alginate lyase homologues revealed distinct patterns depending on the potential lineage of the scaffolds, with evidence of evolutionary relationships among alginolytic gene clusters from Bacteroidetes and Proteobacteria. This information is relevant for understanding carbon fluxes in cold coastal environments and provides valuable information for the development of biotechnological applications from brown algae biomass.