In this paper, we introduce the coevolution-by-coexistence hypothesis which predicts that the strength of a coevolutionary adaptation will become increasingly apparent as long as the corresponding selection from an interacting counterpart continues. Hence, evolutionary interactions between plants and their herbivores can be studied by comparing discrete plant populations with known history of herbivore colonization. We studied populations of the host plant, Filipendula ulmaria (meadow sweet), on six islands, in a Bothnian archipelago subject to isostatic rebound, that represent a spatio-temporal gradient of coexistence with its two major herbivores, the specialist leaf beetles Galerucella tenella and Altica engstroemi. Regression analyses showed that a number of traits important for insect-plant interactions (leaf concentrations of individual phenolics and condensed tannins, plant height, G. tenella adult feeding and oviposition) were significantly correlated with island age. First, leaf concentrations of condensed tannins and individual phenolics were positively correlated with island age, suggesting that plant resistance increased after herbivore colonization and continued to increase in parallel to increasing time of past coexistence, while plant height showed a reverse negative correlation. Second, a multi-choice experiment with G. tenella showed that both oviposition and leaf consumption of the host plants were negatively correlated with island age. Third, larvae performed poorly on well-defended, older host populations and well on less-defended, younger populations. Thus, no parameter assessed in this study falsifies the coevolution-by-coexistence hypothesis. We conclude that spatio-temporal gradients present in rising archipelagos offer unique opportunities to address evolutionary interactions, but care has to be taken as abiotic (and other biotic) factors may interact in a complicated way.