Examination of specimens listed in the original description of Nothobranchius lucius revealed that they belong to two species. Nothobranchius lucius is redescribed based on the type series and other specimens collected in the type locality area, the Kibasira Swamp area, Rufiji River basin, Tanzania, at elevations between 250 and 300 m. Nothobranchius insularis sp. n. is described on the basis of specimens collected in the north part of Mafia Island, Tanzania, at about 10–15 m elevation. Nothobranchius lucius and N. insularis are considered closely related species based on the shared presence of long jaws; caudal fin, in males, with a broad dark grey to black band on its posterior margin; black dots over the whole flank, in females; metapterygoid curved, with its middle and dorsal portions separated from the sympletic by a broad interspace; and posterior process of the quadrate shorter than the ventral length of the quadrate without process. Characters useful to distinguish them include premaxillary dentition, caudal fin shape, colour pattern of flank and unpaired fins in females, fin length, and number of neuromasts of the posterior section of the anterior supraorbital series. Both species are members of a group that also includes N. elongatus, N. hengstleri, N. interruptus, N. jubbi, N. krammeri, and N. melanospilus, which are all diagnosed by the presence of two neuromasts in the anterior section of the anterior supraorbital series.