The introduced jellyfish Aurelia coerulea and the native aeolid nudibranch Austraeolis ornata have co-occurred in Australia since at least 1884. This shared history might have led to a potential, overlooked predator-prey interaction. Here, we tested the hypothesis that A. ornata recognises A. coerulea as prey. We conducted choice experiments to assess the attraction and feeding preference of nudibranchs on polyps and a confirmed sympatric prey, the anemone Actinia tenebrosa. We estimated feeding rates of nudibranchs on polyps and other life stages of the jellyfish: ephyrae and medusae. Finally, we confirmed predator and prey co-occurrence in coastal waters off Australia using data from the Global Biodiversity Information Facility. Austraeolis ornata recognised A. coerulea as prey and was equally attracted to polyps and anemones. Feeding rates on polyps were positively related with nudibranch body size, and predator and prey co-occurred in multiple locations across Australia. Overall, our results provide strong evidence that a long-shared history might have allowed the establishment of a trophic interaction between a native generalist predator and an introduced prey. Understanding how scyphozoans with a long introduction history co-exist with the native community and establish interactions provides insights on their ecology, particularly on potential biological drivers structuring their populations.