Mounting evidence suggests that terrestrialization of plants started in streptophyte green algae, favoured by their dual existence in freshwater and subaerial/terrestrial environments. Here, we present the genomes of Mesostigma viride and Chlorokybus atmophyticus, two sister taxa in the earliest-diverging clade of streptophyte algae dwelling in freshwater and subaerial/terrestrial environments, respectively. We provide evidence that the common ancestor of M. viride and C. atmophyticus (and thus of streptophytes) had already developed traits associated with a subaerial/terrestrial environment, such as embryophyte-type photorespiration, canonical plant phytochrome, several phytohormones and transcription factors involved in responses to environmental stresses, and evolution of cellulose synthase and cellulose synthase-like genes characteristic of embryophytes. Both genomes differed markedly in genome size and structure, and in gene family composition, revealing their dynamic nature, presumably in response to adaptations to their contrasting environments. The ancestor of M. viride possibly lost several genomic traits associated with a subaerial/terrestrial environment following transition to a freshwater habitat.