Understanding the potential outcomes of interactions between native insects and invasive plants is important for predicting the magnitude of effects caused by an invader in its new environment. Here, we investigate the ability of the native western leaf beetle, Chrysochus cobaltinus, and a hybrid of North American Chrysochus species, (hybrid of eastern C. auratus and western C. cobaltinus) to initiate a novel association with introduced pale swallow-wort (Vincetoxicum rossicum) (Apocynaceae). This European vine is invasive in eastern North America but has not yet been encountered by C. cobaltinus in the field. Lab tests demonstrate that C. cobaltinus can feed on introduced V. rossicum foliage, and that they are not locally-specialized to hosts from which they were collected. Thus, adult C. cobaltinus may use V. rossicum as a transient host when encountered in the field. Chrysochus hybrids were unable to feed on introduced V. rossicum (similar to their C. auratus parents) but did feed on native North American Asclepias spp. (similar to their C. cobaltinus parents). Hybridization and subsequent gene introgression may explain both decreased feeding by western C. cobaltinus and increased feeding by eastern C. auratus on native Asclepias spp. in this region, but does not appear to affect feeding on V. rossicum. We predict the potential novel association between native C. cobaltinus and invasive V. rossicum will have a positive or neutral outcome for the beetles, but is unlikely to slow the spread of the vine in North America unless further adaptation occurs.