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. IMPORTANCE Global warming is profoundly influencing the Arctic Ocean. Rapid ice melt and increased freshwater input is increasing ocean stratification, driving shifts in nutrient availability and the primary production that supports marine food webs. Determining bacterial responses to Arctic Ocean change is challenging because of limited knowledge on the specific adaptations of Arctic Ocean bacteria. In this study, we investigated the diversity and genomic adaptations of a globally distributed group of marine bacteria, the Methylophilaceae, in the surface waters of the Arctic Ocean. We discovered a novel lineage of marine Methylophilaceae inhabiting the Arctic Ocean whose evolutionary origin involved a freshwater to marine environmental transition. Crossing the salinity barrier is thought to rarely occur in bacterial evolution. However, given the ongoing freshening of the Arctic Ocean, our results suggest that these relative newcomers to the ocean microbiome increase in abundance and, therefore, ecological significance in a near-future Arctic Ocean.