De eldste funn av representanter for menneskefamilien (Hominidae) er knyttet til tidlig paleolittisk tid. Skjelettmateriale av Homo erectus er funnet ved Ternifine i Algerie, og anslås til å være 600 000–800 000 år gamle. Redskaper av acheuléen type, som er karakteristisk for H. erectus, er også kjent. Funn av moustérien-redskap viser at neandertalmennesket (H. neanderthalensis) har levd i disse områdene i mellompaleolittisk tid. For omkring 40 000 år siden, i senpaleolittisk tid, dukket det moderne mennesket, Homo sapiens, opp.
Capsien-kulturen er navn på en senpaleolittisk jegerkultur i det nåværende Tunisia og Algerie. Den var virksom mellom ca. 10 000 og 6000 år f.Kr. Karakteristisk er funn av kjøkkenmøddinger, noe som tyder på en sesongmessig utnyttelse av resursene. Blant redskaper er funnet mikrolitter og kniver av flint. Til denne perioden kan man datere de første hulemaleriene; særlig kjent er Tassili-funnene på et høydeplatå i det sentrale Sahara, i det nåværende Algerie, der det i 1933 ble funnet huler som viste seg å være rikt dekorert med malerier. De eldste funnene dateres til yngre steinalder, de yngste til tiden omkring Kristi fødsel. Den eldste keramikk i Afrika stammer fra områder i Sahara og kan dateres til ca. 7000 f.Kr.
Ca. 6000 f.Kr. opptrer de første hirsedyrkere, og husdyrhold med geiter og sauer tar til. Den tiltagende uttørkingen fra omkring 5000 f.Kr. fører til at store deler av Sahara blir ubeboelig omkring 3000 f.Kr.