Bacteria inhabiting polar oceans, particularly the Arctic Ocean, are less studied than those at lower latitudes. Discovering bacterial adaptations to Arctic Ocean conditions is essential for understanding responses to the accelerated environmental changes occurring in the North. The Methylophilaceae are emerging as a model for investigating the genomic basis of habitat adaptation, because related lineages are widely distributed across both freshwater and marine ecosystems. Here, we investigated Methylophilaceae diversity in the salinity-stratified surface waters of the Canada Basin, Arctic Ocean. In addition to a diversity of marine OM43 lineages, we report on the genomic characteristics and evolution of a previously undescribed Methylophilaceae clade (BS01) common to polar surface waters yet related to freshwater sediment Methylotenera species. BS01 is restricted to the lower-salinity surface waters, while OM43 is found throughout the halocline. An acidic proteome supports a marine lifestyle for BS01, but gene content shows increased metabolic versatility compared to OM43 and evidence for ongoing genome-streamlining. Phylogenetic reconstruction shows that BS01 colonized the pelagic ocean independently of OM43 via convergent evolution. Salinity adaptation and differences in one-carbon and nitrogen metabolism may play a role in niche differentiation between BS01 and OM43. In particular, urea utilization by BS01 is predicted to provide an ecological advantage over OM43 given the limited amount of inorganic nitrogen in the Canada Basin. These observations provide further evidence that the Arctic Ocean is inhabited by distinct bacterial groups and that at least one group (BS01) evolved via a freshwater to marine environmental transition.