Despite being recorded in Algeria since the nineteenth century, the genus Rhithrogena has never been the object of a taxonomical study and no identified species is known from this country. Investigations of the relict mountain streams of El Kala, north-eastern Algeria, have led to the discovery of a Rhithrogena population. Morphological and molecular analyses identified the species as the Maghrebian endemic Rhithrogena sartorii, so far known only from neighboring Tunisia. We report on the species’ distribution, status, and life cycle and discuss its potential role as a bioindicator in environmental monitoring.