Aux alentours de 814 av. J.-C., les Phéniciens, navigateurs venus de l'Est méditerranéen, fondèrent la ville de Carthage, dans l'actuelle Tunisie. Son rayonnement commercial ne fut effectif qu'après la décadence de Tyr (550 av. J.-C.), leur principale cité. Les Carthaginois établirent des comptoirs sur la côte algérienne (Annaba, Skikda, Alger, etc.). Ils exerçaient une domination économique et politique sur les populations libyco-berbères.

En revanche, les chefs numides savaient mieux jouer des rivalités que la cité développait avec Rome. Ainsi, durant les guerres puniques (IIIe-IIe siècles av. J.-C.), Masinissa, un chef numide allié à Rome, s'empara de Cirta (Constantine). Cette capitale des rois berbères de Masaesyles, dont le territoire s'étendait jusqu'au Maroc oriental, devint alors celle de la Numidie. Après un long règne (203-148 av. J.-C.), Masinissa mourut, laissant le royaume en partage à ses fils, qui composèrent avec les Romains. Mais le petit-fils de Masinissa, Jugurtha, refusa la mainmise romaine ; instigateur d'une insurrection en 111 av J.-C., il devait être soumis par Rome en 105 av. J.-C.

Sous l'autorité romaine, la Numidie devint avec l'Egypte le « grenier de Rome », fournissant blé et huile d'olive. La Maurétanie, annexée à l'Empire romain en 40 apr. J.-C., fut divisée en deux provinces impériales (Maurétanie Tingitane et Maurétanie Césarienne), tandis que l'est de l'Algérie était rattaché à la province proconsulaire d'Afrique. Pour protéger la région des raids des tribus nomades, un réseau de voies militaires fut construit, reliant entre elles des villes de garnison, plusieurs cités de 5 000 à 10 000 habitants, qui furent dotées de tous les attributs des villes romaines (Timgad, Lambèse).

Au IVe siècle apr. J.-C., alors que les légions romaines appelées à défendre l'Empire en déclin, se retirèrent de Numidie, la région fut, pour un temps, déclarée indépendante, sous la pression du mouvement donatiste. La population berbère latinisée, tôt convertie à la foi chrétienne, s'était en effet massivement ralliée à cette secte chrétienne, persécutée par les autorités romaines, après que le christianisme fut devenu religion officielle de l'Empire (313), tandis que les tribus berbères des montagnes, non latinisées, continuaient à résister. Dans un contexte d'anarchie, les Vandales, peuple germanique, envahirent l'Afrique du Nord et y établirent un royaume en 429. Leur domination, limitée à la bande côtière, resta cependant fragile, et des principautés berbères indépendantes purent se reconstituer durant cette période.

En 533, les Vandales furent chassés par les armées de l'empereur byzantin, Justinien Ier, dont le rêve était de faire renaître la splendeur de l'Empire romain. La conquête byzantine, pourtant, se limita seulement à l'est du pays.