The evolution of parasitism is a recurring event in the history of life and a core question in evolutionary biology. Trypanosomatids are important parasites including the human pathogens Trypanosoma brucei, T. cruzi and Leishmania spp., which have evolved complex life cycles to exploit a series of defined host environments after diverging from free-living, phagotrophic bodonids. However, the origins of genomic adaptations for transmission, disease and pathogenesis remain obscure because there has been no genomic comparison of parasitic and free-living species. Addressing this absence, we have produced a genome sequence for Bodo saltans, the closest known non-parasitic relative of trypanosomatids. Here we show how genomic reduction and innovation contributed to the character of trypanosomatid genomes. We find that despite a genetic ‘streamlining’ of diverse physiological functions, including macromolecular degradation and cellular homeostasis, the origin of trypanosomatid parasitism did not lead to a substantial reduction in genome function. Instead, we observe dramatic elaboration of gene families that facilitate host-parasite interactions and pathogenesis. We also show how parasite-specific proteins that characterize the enigmatic cell surfaces of Trypanosoma and Leishmania were derived from the same ancestral proteins, still represented in B. saltans. Our new evidence distinguishes adaptive innovations of trypanosomatids that post-date their parasitic origin from essentially kinetoplastid legacies of a free-living past. It shows that when the labile environment of a phagotrophic ancestor was replaced by the defined conditions of their various hosts, trypanosomatid physiology was reoriented towards host interaction, and ancestral structures were radically transformed to provide adaptations for obligate parasitism.