Bioerosional trace fossils (borings) are reported for the first time in Algeria. Three ichnotaxa observed in the shells of Ostrea lamellosa from the lower Messinian (upper Miocene) deposits of the Tafna basin (NW Algeria) are described. The ichnotaxa are Entobia cf. geometrica, Gastrochaenolites cf. torpedo and Trypanites isp.. Ostrea lamellosa shells are encrusted by balanid barnacles which are bored by Trypanites isp.. The ichnoassemblage is assigned to the Trypanites ichnofacies. Besides the bioerosion and encrustation described herein, specimens permitted the identification of the different phases of the Messinian transgression across the Souk el Khemis shoal.