In the Saoura Valley (Ougarta Basin, Saharan Algeria), the lower–upper Famennian part of the essentially shally Marhouma Formation is characterized by deep-water facies and includes horizons rich in ammonoids (goniatites and clymeniids) and blind to eye-reduced phacopide trilobites. They are also rich in small-sized and smooth rhynchonellide brachiopods, investigated here for the first time in order to detail their post-Kellwasser recovery. Rhynchonellides clearly predominate in the brachiopod assemblages (representing 90% of the whole assemblage, with 10 species) composed otherwise of athyridides, orthides and spiriferides. Rhynchonellides are mostly represented by relatively flat leiorhynchids and rozmanariids consistent with poor oxygenation on the sea floor. One new species is described (Evanidisinurostrum saouraense sp. nov.); four genera, previously known only from the south-eastern margin of Laurussia, are reported for the first time from the northern margin of Gondwana: the leiorhynchid Sphaeridiorhynchus and the rozmanariids Leptoterorhynchus, Pugnaria and Novaplatirostrum.