Ivy (Hedera spp. Araliaceae) is a polyploid complex of woody vines. Native to Eurasia and northern Africa ivy is cultivated worldwide and has become an aggressive invader of North American forests. Despite its ecological impacts and economic significance to the horticultural industry the taxonomy of Hedera is controversial and historical relationships are poorly defined. Here we characterize the phylogeny of Hedera based on the low-copy nuclear locus Granule-bound starch synthase I (GBSSI) and twelve non-coding cpDNA regions. Maximum parsimony and Bayesian analyses of both data sets identified Hedera as monophyletic. For GBSSI we isolated eighteen haplotypes that were widely shared across species. There was no evidence of fixed heterozygosity or haplotype additivity in polyploids suggesting possible autopolyploid origins. For cpDNA we isolated sixteen haplotypes that were highly structured by geography. Haplotype diversity and phylogenetic structure were greatest in northern Africa and southern Europe. Thus while most members of the Araliaceae reside in tropical and subtropical Asia the early diversification of Hedera probably occurred in the Mediterranean Basin. Geographically-structured clades included diploid and polyploid species suggesting that genome duplication has occurred repeatedly in the genus. Closely-related ivies often differed in leaf size and trichome morphology indicating evolutionary lability of traits traditionally used for classification. Nonetheless we recovered similar or identical DNA sequences within morphologically-defined species. Notable exceptions included southern populations of H. helix (H. helix subsp. caucasigena and H. helix subsp. rhizomatifera) that had cpDNA haplotypes distinct from those of central and northern Europe (H. helix subsp. helix).