Genealogical discordance, or when different genes tell distinct stories although they evolved under a shared history, often emerges from either coalescent stochasticity or introgression. In this study, we present a strong case of mito-nuclear genealogical discordance in the Australian rainforest lizard species complex of Saproscincus basiliscus and S. lewisi. One of the lineages that comprises this complex, the Southern S. basiliscus lineage, is deeply divergent at the mito- chondrial genome but shows markedly less divergence at the nuclear genome. By placing our results in a comparative context and reconstructing the lineages’ demography via multi-locus and coalescent-based Approximate Bayesian Computation (ABC) methods, we test hypotheses for how coalescent variance and introgression contribute to this pattern. These analyses suggest that the observed genealogical discordance likely results from introgression. Further, to generate such strong discordance, introgression probably acted in concert with other factors promoting asymmetric gene flow between the mitochondrial and nuclear genomes, such as selection or sex-biased dispersal. This study offers a framework for testing sources of genealogical discordance and suggests that historical introgression can be an important force in shaping the genetic diversity of species and their populations.