Catfishes of the subfamily Trichomycterinae comprise the most diverse fish group with species adapted to live in Neotropical caves, but past evolutionary scenarios that have driven the origin of these troglobitic species remain unknown. We herein investigate the phylogenetic position of the cave-restricted Trichomycterus rubbioli, endemic to the semi-arid Caatinga of northeastern Brazil, through a time-calibrated molecular phylogenetic analysis of a broad sample of trichomycterine taxa (84 spp), using two nuclear and two mitochondrial genes (3030 bp). The analysis supported T. rubbioli as a member of the Trichomycterus s.s. clade endemic to eastern South America and an early Miocene origin for the T. rubbioli lineage. The combination of available data suggests that the T. rubbioli lineage adapted to the troglobitic lifestyle between the Middle and Late Miocene, a period when the semi-arid conditions of the Caatinga biome became established and consequently streams of the region became seasonal. This past scenario would be responsible for extinction of epigean trichomycterines while preserving the lineage within the cave system. Morphological characters of the troglobitic 'Trichomycterus' itacarambiensis from the transition area between the Cerrado and the Caatinga indicate distant relationships with T. rubbioli, suggesting an independent evolutionary event of cave colonization.