The Sebkha el Melah, located near the Libyan-Tunisian border, is fringed by a relict stromatolite-serpulid belt. These bioherms developed 5500 years ago during the Flandrian sea-level highstand when the area of the present-day sebkha was covered by a wide restricted lagoon. Relict lagoonal beaches and spits, mainly composed of cerebroid ooids and cerithid gastropods, are flanked by mushroom-shaped stromatolites reaching up to 50 cm in height. These stromatolites grew on top of small serpulid bioherms as well as on top of beachrock and beachrock blocks in a shallow subtidal pre-evaporitic realm. The primary porosity of these bioherms is obliterated by botryoidal and spherulitic aragonite, probably of microbial origin. This sub-Recent association of stromatolites, serpulid bioherms and cerebroid ooids provides a useful additional model for the interpretation of upper Paleozoic deposits, where similar facies have been described.