Comme beaucoup de contrées du Sahara, la région a été peuplée très tôt. La faune et la flore étaient plus développées qu'aujourd'hui, et le sol garde des vestiges de cette époque éloignée. C'est ainsi qu'en 1957, on a découvert, à Hassi Khlifa, un mammouth, ce qui fait que le Sahara a connu, à cette époque, une période de glaciation. Il y a plusieurs milliers d'années, le Sahara a connu des périodes humides et, à partir du quaternaire, une succession de périodes humides et de périodes sèches. Le Sahara était couvert de grands lacs et d'une savane de type tropical, où vivaient de nombreuses espèces animales. On sait que vers 18 000 et 13 000 avant J.-C., le Sahara se transforme même en désert de glace, en raison des relais de la glaciation de Würm, dans le continent nord. La fonte de la calotte glaciaire, un millénaire après, va marquer le retour des pluies sur le Sahara qui va se couvrir d'une belle couverture végétale. Au moment de la construction de l'aéroport, on a également exhumé de nombreux vestiges de la préhistoire : des lames, des bifaces, des silex… Déjà, les Berbères Garamantes peuplaient la région au cours du premier millénaire avant J.-C.
