Cynolebias gilbertoi n. sp. is described from a temporary pond near the rio São Francisco, in Estado da Bahia, northeastern Brazil. It is considered to be a member of the Cynolebias porosus species-complex by having the tip of the interarcual cartilage displaced to posterior portion of second pharyngobranchial, a distinct ossification ventral to basibranchial cartilage, two distinct transverse rows of neuromasts above opercular region, and a distal portion of anal fin of males pale blue on fin membrane and red on rays. The new species differs from all other species of that complex by having many teeth on vomer, fewer vertebrae and scales in longitudinal series, and the pelvic fins separated by a wide interspace. It is hypothesized to be most closely related to C. perforatus and C. leptocephalus, its only congeners also possessing teeth on vomer and numerous neuromasts on the ventral part of opercular region.