Interactions between species have catalyzed 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 long evolutionary timescales, spatial isolation, or other exogenous processes. Here 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. Initially, nested patterns form through an arms race where hosts successively lose the original receptor (LamB) and phages evolve to use a second (OmpC) and then a third (OmpF) receptor. Next, modules form when the cost of losing the third receptor, OmpF, increases and bacteria evolve resistance mutations that modify the OmpF receptors’ extramembrane loops. In turn, phages evolve adaptations that facilitate specialized interactions with different OmpF variants. Nestedness reemerges within modules as bacteria evolve increased resistance and phages enhance infectivity against module-specific receptor variants. 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.