Brown seaweeds are keystone species of coastal ecosystems, often forming extensive underwater forests, that are under considerable threat from climate change. Despite their ecological and evolutionary importance, this phylogenetic group, which is very distantly related to animals and land plants, is still poorly characterised at the genome level. Here we analyse 60 new genomes that include species from all the major brown algal orders. Comparative analysis of these genomes indicated the occurrence of several major events coinciding approximately with the emergence of the brown algal lineage. These included marked gain of new orthologous gene families, enhanced protein domain rearrangement, horizontal gene transfer events and the acquisition of novel signalling molecules and metabolic pathways. The latter include enzymes implicated in processes emblematic of the brown algae such as biosynthesis of the alginate-based extracellular matrix, and halogen and phlorotannin biosynthesis. These early genomic innovations enabled the adaptation of brown algae to their intertidal habitats. The subsequent diversification of the brown algal orders tended to involve loss of gene families, and genomic features were identified that correlated with the emergence of differences in life cycle strategy, flagellar structure and halogen metabolism. We show that integration of large viral genomes has had a significant impact on brown algal genome content and propose that this process has persisted throughout the evolutionary history of the lineage. Finally, analysis of microevolutionary patterns within the genusEctocarpusindicated that deep gene flow between species may be an important factor in genome evolution on more recent timescales.