AbstractHistorical contingency broadly refers to the proposition that even random historical events can constrain the ecological and evolutionary pathways of organisms and that of entire communities. Focusing on communities, these pathways can be reflected into specific structural changes within and across trophic levels – how species interact with and affect each other – which has important consequences for species coexistence. Using the registry of the last 2000 years of plant introductions and their novel herbivores encountered in Central Europe, we find that the order of arrival of closely related (but not of distantly related) plant species constrained the structural changes within the trophic level formed by herbivore species across the observation period. Because it is difficult for field and lab experiments to be conducted over hundreds of years to record and replay the assembly history of a community, our study provides an alternative to understand how structural changes have occurred across extensive periods of time.