The most abundant aquatic microbes are small in cell and genome size. Genome-streamlining theory predicts gene loss caused by evolutionary selection driven by environmental factors, favouring superior competitors for limiting resources. However, evolutionary histories of such abundant, genome-streamlined microbes remain largely unknown. Here we reconstruct the series of steps in the evolution of some of the most abundant genome-streamlined microbes in freshwaters ("Ca. Methylopumilus") and oceans (marine lineage OM43). A broad genomic spectrum is visible in the family Methylophilaceae (Betaproteobacteria), from sediment microbes with medium-sized genomes (2-3 Mbp genome size), an occasionally blooming pelagic intermediate (1.7 Mbp), and the most reduced pelagic forms (1.3 Mbp). We show that a habitat transition from freshwater sediment to the relatively oligotrophic pelagial was accompanied by progressive gene loss and adaptive gains. Gene loss has mainly affected functions not necessarily required or advantageous in the pelagial or is encoded by redundant pathways. Likewise, we identified genes providing adaptations to oligotrophic conditions that have been transmitted horizontally from pelagic freshwater microbes. Remarkably, the secondary transition from the pelagial of lakes to the oceans required only slight modifications, i.e., adaptations to higher salinity, gained via horizontal gene transfer from indigenous microbes. Our study provides first genomic evidence of genome reduction taking place during habitat transitions. In this regard, the family Methylophilaceae is an exceptional model for tracing the evolutionary history of genome streamlining as such a collection of evolutionarily related microbes from different habitats is rare in the microbial world.