The red-toothed shrews (Soricinae) are the most widespread subfamily of shrews, distributed from northern South America to North America and Eurasia. Within this subfamily, the tribe Nectogalini includes the fossil species Nesiotites hidalgo recorded from the Late Pleistocene to Holocene of the Balearic Islands (Western Mediterranean). Although there is a consensus about the close relationship between the extinct red-toothed shrew genera Nesiotites and Asoriculus based on morphology, molecular data are necessary to further evaluate the phylogenetic relationships of the Balearic fossils. We obtained a near complete mitochondrial genome of N. hidalgo, allowing the first molecular phylogenetic analysis of this species. Analyses based on 15,167 bp of the mitochondrial genome placed N. hidalgo as close relative to the extant Himalayan shrew (Soriculus nigrescens), and a combined analysis using molecular and morphological data confirm that N. hidalgo and Asoriculus gibberodon are sister-taxa with S. nigrescens as the immediate outgroup. Molecular clock and divergence estimates suggest that the split between N. hidalgo and its closest living relative occurred around 6.44 Ma, which is in agreement with the previously proposed colonisation of the Balearic Islands from mainland Europe by nectogaline shrews during the Messinian Salinity Crisis (5.97–5.33 My ago). Our results highlight that it is possible to retrieve genetic data from extinct small mammals from marginal environments for DNA preservation. Additional finds from the fossil record of Soricinae from the Eurasian Late Miocene/Early Pliocene are needed to shed further light on the still confusing taxonomy and paleobiogeography of this clade.