Ingen säker kunskap finns om berbernas ursprung. Den neolitiska capsienkulturen som existerade i Nordafrika 10 000 f.Kr.-6 000 f.Kr. brukar associeras med berberna och spridningen av de afroasiatiska språken. Capsienkulturens ursprung har dock inte gått att fastställa arkeologiskt.

Lingvistiska teorier antyder ett nära släktskap mellan berberspråken och tchadspråk och nubiska språk.

Berbernas genuppsättning följer ett mönster där tuareger i Sahara har omkring 80 procent subsahariska gener, medan motsvarande siffra för till exempel rifkabyler i nordvästra Algeriet bara är 4 procent.

Redan de äldsta egyptiska, grekiska och romerska skrivna källorna nämner berber i norra Afrika. De dyker första gången upp i egyptiska texter som beskriver ett krig mot "libu" (libyer) vid rikets västra gräns. Bysantinska krönikörer beklagade sig ofta över berbiska attacker på perifera kloster.

Till skillnad från tidigare invasioner och koloniseringar fick den arabisk-islamiska utbredningen i Nordafrika bestående och djupgående inverkan i området. Den nya tron, i sina olika former, påverkade i stort sett alla samhällets delar. Den förde med sig arméer, lärda män och mystiker som till stora delar ersatte befintlig stamlojalitet och -kultur med nya sociala och politiska normer.

Islamiseringen och arabiseringen av regionen var dock en långvarig och komplicerad process. Berbiska nomader lät sig snabbt omvändas och assisterade den arabiska invasionen, men de kristna och judiska grupperna hade inte blivit helt marginaliserade förrän under den almohadiska dynastin på 1100-talet.

Den första arabiska militära expeditionen 642–669 var början på islams spridning i Nordafrika. De första räderna från baser i Egypten kom till som lokala initiativ snarare än på centrala order från kalifatet. När umayyaddynastin 661-750 flyttade sin huvudstad från Medina till Damaskus gjorde deras strävan att dominera Medelhavet det strategiskt nödvändigt att flytta fram sina positioner i norra Afrika. År 670 grundade så en arabisk armé under Uqba ibn Nafi staden Kairouan omkring 160 kilometer söder om dagens Tunis som fick tjäna som bas för fortsatta militära operationer.

Uqbas efterträdare Abu al-Muhajir Dinar förde expansionen vidare västerut in i Algeriet, där han lyckades ingå en överenskommelse med ledaren för det berbiska, kristna förbundet, Kusayla, som lät sig omvändas till islam. Tlemcen förstördes och huvudstaden flyttades till Takiwan nära Kairouan. Snart uppstod dock komplikationer och berbiska och arabiska styrkor kontrollerade omväxlande området fram till 697. År 711 hade umayyaderna med berbernas stöd lyckats ta kontrollen över hela Nordafrika. Från Kairouan styrde kalifatets guvernörer över Ifriqiya, en provins som sträckte sig från västra Libyen till östra Algeriet.

Trots att berberna tog till sig islam innebar inte det att de utan reservationer stödde det arabiska kalifatet som tyngde berberna med höga skatter, behandlade de nyomvända som andra klassens muslimer och till och med förslavade dem. Det utbredda missnöjet med kalifatet ledde 739-40 till en öppen kharijitisk revolt. Kharijiterna, som vände sig mot den fjärde kalifen Ali ibn Abi Talib som 657 undertecknat en fred med umayyaderna, hade bekämpat umayyaderna österut och deras egalitära idéer attraherade många berber. Till exempel ansåg kharijiterna att alla muslimer kunde väljas till kalif oavsett etnicitet, ursprung eller släktskap med profeten Muhammed.

Efter revolten etablerade kharijiterna ett antal teokratiska stamriken som i allmänhet fick en kort och dramatisk historia. Några av dem, till exempel Sijilmasa och Tlemcen som låg vid viktiga handelsvägar, visade sig dock livskraftiga. 750 flyttade umayyadernas efterträdare abbasiderna kalifatets huvudstad till Bagdad och återinförde kalifatets kontroll över provinsen genom att tillsätta guvernören Ibrahim ibn al Aghlab. Aghlabiderna tjänade visserligen officiellt kalifatet, men provinsen förblev i praktiken ett självständigt område fram till 909 och hovet i Kairouan blev ett viktigt kulturellt centrum.

Väster om aghlabiderna regerade Abd ar-Rahman ibn Rustam och från sin huvudstad Tiaret sydväst om Alger kontrollerade han större delen av Maghrebområdet. Rustamidernas imamat styrdes 761-909 av ibadiska, kharijitiska imamer som valdes av inflytelserika medborgare. Dessa imamer blev kända för sin ärlighet, fromhet och rättvisa, och hovet i Tiaret blev ett betydande lärosäte för matematik, astronomi och astrologi vid sidan av teologi och juridik. Imamerna misslyckades dock med att hålla en stående armé och 909, då den rustamidiska dynastin degenererat till dekadens, kunde fatimiderna störta den.

Majoriteten av de muslimer som inledde erövringen av Spanien 711 var berber och de leddes av den berbiske fältherren Tariq ibn Zyiad, som var länsherre under kalifen i Damaskus Abd al-Malik och hans nordafrikanske vicekung Musa ibn Nusayr. Berberna slog sig ned i Kantabriska bergen, Iberiska bergen och bland bergen i Andalusien. Under Nusayr ledde den andra berbisk-arabiska armé som gjorde sitt intåg i Spanien 712. Armén sägs ha utgjort 66 procent av den muslimska befolkningen i Spanien, och orsaken till att de hjälpte den umayyadiske kalifen Abd ar-Rahman I i Spanien var förmodligen att hans mor var en berbisk kvinna. Flera av de muslimska stadsstater i Spanien efter kalifatets upplösning 1031, de så kallade Taifa-kungadömena, hade berbiska härskare, till exempel de ziridiska kungarna i Granada liksom härskarna i Toledo, Badajoz och Málaga. Hela Taifa-perioden avslutades med att de berbiska almoraviderna (från dagens Mauretanien) övertog kontrollen över Spanien vid slutet av 1000-talet. Deras efterträdare, almohaderna, (också de berber) införde en strikt tolkning av islam under andra hälften av 1100-talet samtidigt som de bejakade filosofiskt tänkande.