Interactions between species catalyze the evolution of multiscale ecological networks, including both nested and modular elements that regulate the function of diverse communities. One common assumption is that such complex pattern formation requires spatial isolation or long evolutionary timescales. We show that multiscale network structure can evolve rapidly under simple ecological conditions without spatial structure. In just 21 days of laboratory coevolution, Escherichia coli and bacteriophage Φ21 coevolve and diversify to form elaborate cross-infection networks. By measuring ~10,000 phage-bacteria infections and testing the genetic basis of interactions, we identify the mechanisms that create each component of the multiscale pattern. Our results demonstrate how multiscale networks evolve in parasite-host systems, illustrating Darwin's idea that simple adaptive processes can generate entangled banks of ecological interactions.