As invasive species spread, the ability of local communities to resist invasion depends on the strength of biotic interactions. Evolutionarily unused to the invader, native predators or herbivores may be initially unskilled or wary of consuming newcomers, allowing them to proliferate. However, these relationships may be highly dynamic, and novel consumer-resource interactions could form as familiarity grows. Here, we explore the development of effective biotic resistance towards a highly invasive alga in the Mediterranean using multiple space-for-time approaches. We show that the principal native Mediterranean herbivore learns to consume the invader species within less than a decade. At recently invaded sites, the herbivore actively avoided the alga, shifting to distinct preference and high consumptions at older sites, even when invader abundance was low. This rapid strengthening of the interaction contributed to the eventual collapse of the alga after an initial dominance. Therefore, our results stress the importance of conserving key native populations to allow communities to develop effective resistance mechanisms against invaders with time.