Two new species of Cynolebias are described from temporary pools of the Verde Grande River drainage, São Francisco basin, in the semiarid Caatinga, a phytogeographical province of northeastern Brazil. Cynolebias elegans sp. n., a member of the C. gilbertoi group, is considered as the smallest species of the genus, reaching about 38 mm of standard length; it is distinguished from all other species of the group by the long unpaired fins, relative position of anal fin and vertebrae, and morphometric data. Cynolebias gorutuba sp. n. belongs to the Cynolebias zeta-clade, a group of large species supposedly feeding on smaller sympatric seasonal killifishes; it differs from other species of the group by the female colour pattern, relative position of dorsal fin and vertebrae, and cephalic neuromast pattern. Both species herein described were not found in recent collecting trips, after their habitats had been drastically modified, and are also possibly highly endangered if not already extinct. Field data relative to gradual habitat decline in the type locality region of C. elegans indicate that after pools lose the dense vegetation that provides shelter to small species, these species such as C. elegans become exposed to larger sympatric predatory species and are extirpated. These data support the hypothesis that small seasonal killifish species specialised in living within marginal shaded areas of temporary pools are more susceptible to environmental changes than other congeners.