Contemporary adaptation of plant feeding insects to introduced hosts provides clear cases of ecologically based population divergence. In most cases the mechanisms permitting rapid differentiation are not well known. Here we study morphological and genetic variation associated with recent shifts by the Australian soapberry bug Leptocoris tagalicus onto two naturalized Neotropical balloon vines, Cardiospermum halicacabum and C. grandiflorum that differ in time since introduction. Our results show that these vines have much larger fruits than the native hosts (Whitewood tree –Atalaya hemiglauca– and Woolly Rambutan –Alectryon tomentosus–) and that bugs living on them have evolved significantly longer beaks and new allometries. Genetic analyses of mitochondrial haplotypes and amplified fragment length polymorphic (AFLP) markers indicate that the lineage of bugs on the annual vine C. halicacabum, the older introduction, is intermediate between the two subspecies of L. tagalicus found on native hosts. Moreover, where the annual vine and Whitewood tree co-occur together, the morphology and genomic composition of the bugs are similar to those occurring in allopatry. These results show that hybridization provided the genetic elements underlying the strongly differentiated ‘Halicacabum bugs’. In contrast, the bugs feeding on the recently introduced perennial balloon vine (C. grandiflorum) showed no evidence of admixture, and are genetically indistinguishable from the nearby populations on a native host.