A new species of Megaleporinus is described from the Rio de Contas, a coastal drainage of eastern Brazil, and its phylogenetic relationships are studied using molecular data. The new species is unique among Anostomidae by possessing two exclusive features: an irregular dark longitudinal stripe from supracleithrum to second midlateral blotch and anterior cranial fontanel partially closed. In addition, the new species is diagnosed by having three premaxillary teeth, three dentary teeth, 37 or 38 scales in lateral line, 16 scale rows around caudal peduncle, three dark midlateral blotches on body, and red fins in life. The new species is closely related to M. obtusidens from the São Francisco basin, corroborating previous studies that indicated that the latter represents a species complex as currently defined. The new species exhibits the first rib enlarged in mature males, a feature described for some congeners. The new species is herein considered to be Endangered under the IUCN criteria.