A fundamental question in marine microbial ecology is how microbes adapt to ocean environments. Although numerically dominant populations are typically considered more successful, higher census population sizes (Nc) do not equate directly to a greater capability for adaptation. Instead, effective population size (Ne) determines the fate of deleterious and favourable mutations, and thus is a key parameter for determining the adaptive potential of a population. In the case of the SAR11 and Roseobacter lineages, two abundant heterotrophic bacteria in ocean surface waters with contrasting life history strategies, culture-independent population surveys suggest that SAR11s have greater Nc than Roseobacters. To determine relative Ne, we compared the ratio of nonsynonymous to synonymous substitution rates (ω) of recently diverged lineages of these taxa. Values of ω associated with several of the Roseobacter subclades were lower than for SAR11 subclades, suggesting greater Ne in these cases. Most Roseobacter lineages also had smaller ω values compared with an atypical basal Roseobacter lineage with a large Nc. This finding provides insight into variability in Ne across two important marine bacterial lineages, and provides an evolutionary context for considering how heterotrophic marine bacteria may differ in their ability to adapt to changing ocean habitats.