The genus Moenkhausia is among the most species-rich genera in the family Characidae. Among its species, four occur in the Northeastern Mata Atlântica (NMAF) and São Francisco (SF) freshwater ecoregions; however, only Moenkhausia costae is distributed across both ecoregions. The species was originally described from the São Francisco river basin but also occurs in the NMAF, specifically in the Itapicuru river basin. This distribution is consistent with the hypothesis that the Itapicuru and Vaza-Barris rivers were tributaries of an ancient drainage system that included the main channel of the middle São Francisco river. Although the occurrence of shared fish species between the NMAF and SF ecoregions represents an initial starting point for understanding the biogeographic history of the rivers that drain these regions, population-level studies are still incipient. In this context, the present study aimed to investigate, describe, and analyze the phylogeographic pattern of M. costae across the NMAF and SF ecoregions. To this end, mitochondrial COI sequences were obtained and analyzed from samples collected throughout the hydrographic basins where the species occurs. This study reports the first record of M. costae in the Jequitinhonha river basin (NMAF), expanding its known distribution farther south within the ecoregion. Phylogenetic analysis recovered the monophyly of the species with strong statistical support. Haplotype network revealed three haplotypes: one exclusive and two shared. A subtle genetic structuring was also observed between populations from the NMAF and SF. However, populations from the Itapicuru and Jequitinhonha river basins also shared haplotypes with populations from the São Francisco. Although preliminary, these results provide additional support for the hypothesis of historical connectivity between the São Francisco and Northeastern Mata Atlântica freshwater ecoregions.