The study of herbivorous insects underpins much of the theory that concerns the evolution of species interactions. In particular, Pieridae butterflies and their host plants have served as a model system for studying evolutionary arms races. To learn more about the coevolution of these two clades, we reconstructed ancestral ecological networks using stochastic mappings that were generated by a phylogenetic model of host-repertoire evolution. We then measured if, when, and how two ecologically important structural features of the ancestral networks (modularity and nestedness) evolved over time. Our study shows that as pierids gained new hosts and formed new modules, a subset of them retained or recolonised the ancestral host(s), preserving connectivity to the original modules. Together, host-range expansions and recolonisations promoted a phase transition in network structure. Our results demonstrate the power of combining network analysis with Bayesian inference of host-repertoire evolution to understand changes in complex species interactions over time.