The New Zealand stick insect genus Acanthoxyla Uvarov is extremely unusual among higher taxa of animals in that all known species are obligate parthenogens. We have used a combination of the mitochondrial DNA genes cytochrome oxidase subunits I and II, 28S nuclear ribosomal RNA, and the two single-copy nuclear genes elongation factor 1alpha and phosphoglucose isomerase to test hypotheses on the role of hybridization in the evolution of this genus. Alleles at the single-copy nuclear loci in three sampled species of Acanthoxyla were resolved by cloning the PCR products. Analysis of multilocus genotypes shows that most sampled individuals of Acanthoxyla possess three alleles at the single-copy nuclear loci, which we have interpreted to indicate triploidy. Because most of the alleles from Acanthoxyla form a monophyletic group, including sets of alleles possessed by the putative triploids, we have inferred that the extant parthenogenetic lineages formed via hybridization between species of Acanthoxyla, at least one of which must have been sexual. More recently, there have been multiple introgression events from the related species Clitarchus hookeri White, although C. hookeri does not appear to be involved with the origin of parthenogenesis in Acanthoxyla. Our study demonstrates the utility of cloning alleles from multiple single-copy nuclear genes for resolving the origins of parthenogenetic lineages.