A new species of Neoplecostomus is described from the rio Doce basin representing the first species of this genus in the basin. The new species is distinguished from its congeners byenlarged, fleshy folds between dentaries, two or three series of developed papillae anterior to premaxillary teeth and a adipose-fin membrane present, and by lacking enlarged odontodes along snout lateral margins in mature males, a well-developed dorsal-fin spinelet wider than dorsal-fin spine base, lower number of lateral-line plates and developed membrane on the dorsal portion of the first, second and third pelvic-fin branched rays. Additionally, we present a brief discussion of biogeographic scenarios that may explain the distribution of the new species in the rio Doce basin. We suggested that the ancestral lineage of the new species reached the rio Doce from the upper portions of rio Paraná drainages about 3.5 Mya (95% HPD: 1.6–5.5) indicating a colonization route of the N. doceensis ancestral lineage from the south end of Serra do Espinhaço, probably as a result of headwater capture processes between the upper rio Paraná and rio Doce basins.