We have applied Bayesian and maximum likelihood methods of phylogenetic estimation to data from four mitochondrial genes (COI, COII, 12S, and 16S) and a single nuclear gene (EF1α) from several genera of New Zealand, Australian, and New Caledonian cicada taxa. We specifically focused on the heterogeneity of phylogenetic signal among the different data partitions and the biogeographic origins of the New Zealand cicada fauna. The Bayesian analyses circumvent many of the problems associated with other statistical tests for comparing data partitions. We took an information-theoretic approach to model selection based on the Akaike Information Criterion (AIC). This approach indicated that there was considerable uncertainty in identifying the best-fit model for some of the partitions. Additionally, a large amount of uncertainty was associated with many parameter estimates from the substitution model. However, a sensitivity analysis on the combined dataset indicated that the model selection uncertainty had little effect on estimates of topology because these estimates were largely insensitive to changes in the assumed model. This outcome suggests strong signal in our data. Our analyses support a New Caledonian affiliation of the New Zealand cicada genera Maoricicada, Kikihia, and Rhodopsalta and Australian affinities for the genera Amphipsalta and Notopsalta. This result was surprising, given that previous cicada biologists suspected a close relationship between Amphipsalta, Notopsalta, and Rhodopsalta based on genitalic characters. Relationships among the closely related genera Maoricicada, Kikihia, and Rhodopsalta were poorly resolved, the mitochondrial data and the EF1α data favoring different arrangements within this clade.