Ediacara-type body fossils are reported here for the first time from the West African craton in Algeria. This assemblage comprises medusoids comparable to Medusinites sp. and Nimbia, a trace fossil, and a new genus of body fossil with uncertain affinity. The fossils are in sandstones of the Neoproterozoic cover, separated by a major unconformity from the overlying tillite, considered until now to be late Neoproterozoic. Most Ediacaran fauna radiated after the Varanger ice age, and tillites—associated in Ahaggar with molasse of the Pan-African belt—are overlain by carbonates that were deposited during deglaciation and that locally contain Early Cambrian shelly fossils; therefore, we interpret the glaciogenic diamictite as Early Cambrian in age.