Species of burrowing animals have changed substantially over evolutionary time scales, but, surprisingly, burrows display persisting morphological patterns throughout the Phanerozoic. Deep-sea burrows are geometrically patterned, whereas shallow-marine burrows display simpler morphologies. This divergence between burrow associations is one of the central conundrums of paleontology, but it has never been quantitatively demonstrated, and the organizing principles responsible for this structure remain unknown. We show that the divergence of burrow associations has been shaped by small-world dynamics, which is proposed as a major macroevolutionary force in marine environments. Using network analysis, our study reveals that the association patterns between burrow morphotypes in 45 paleontological sites span ∼500 m.y. Strong statistical support is demonstrated for a surprising association pattern, according to which the data set is optimally partitioned into two subgroups of tightly associated burrow types. These groups correspond to shallow- and deep-marine biomes. Our analysis demonstrates that across the Phanerozoic Eon, burrows did not assemble randomly nor regularly, following instead small-world assembly rules remarkably similar to those that shape human social networks. As such, small-world dynamics deeply influenced gene flow and natural variation in heritable behavior across evolutionary time.