Fishes of the genus Eleotris present highly conserved morphology, which may make their recognition difficult. Here, two cryptic Eleotris lineages from five locations along the coast of Brazil were identified using the COI gene and two nuclear fragments. High bootstrap and posteriori values supported those lineages, and the genetic distance of COI varied from 6% between the two lineages to 14.1% from other western Atlantic Eleotris species, such as E. pisonis, E. amblyopsis and E. perniger. The reciprocal monophyly for both types of markers, the divergences between those lineages and the other Eleotris species from the Brazilian coast may, in fact, represent two new cryptic species. The cryptic lineages and currently recognized species were collected in distinct environments, reinforcing the need for further sampling to understand the real distribution of each taxon.