Rhynchocyon udzungwensis is a recently described and poorly understood sengi (giant elephant-shrew) endemic to two small montane forests in Southern Tanzania, and surrounded in lower forests by R. cirnei reichardi. In this study, we investigate the molecular genetic relationship between R. udzungwensis and R. c. reichardi, and the possible role that shifting species distributions in response to climate fluctuations may have played in shaping their evolutionary history. Rhynchocyon udzungwensis and R. c. reichardi individuals were sampled from five localities for genetic analyses. Three mitochondrial and two nuclear loci were used to construct species trees for delimitation and to determine whether introgression was detectable either from ancient or ongoing hybridization. All species-tree results show R. udzungwensis and R. c. reichardi as distinct lineages, though mtDNA shows evidence of introgression in some populations. Nuclear loci of each species were monophyletic, implying introgression is exclusively historical. Because we found evidence of introgression, we used distribution data and species distribution modelling for present, glacial, and interglacial climate cycles to predict how shifting species distributions may have facilitated hybridization in some populations. Though interpretations are affected by the limited range of these species, a likely scenario is that the mtDNA introgression found in eastern mid-elevation populations was facilitated by low numbers of R. udzungwensis that expanded into lowland heavily occupied R. c. reichardi areas during interglacial climate cycles. These results imply that relationships within the genus Rhynchocyon may be confounded by porous species boundaries and introgression, even if species are not currently sympatric.