Sidi Okba et la Kahena, deux figures de légende ou d'épopée, viennent illustrer cette période si agitée pendant laquelle les arabes envahisseurs firent aux tribus berbères une guerre sans merci.

Sidi Okba, avec le sabre et le Coran, chef illuminé et impitoyable, entraîne à sa suite des soldats sanguinaires (l'an 46 de l'Hégire). Maître de l'Est, il se précipite vers le Maghreb. Rien ne lui résiste. Seuls les berbères de l'Aurès, sous la conduite de Koceïla, relèvent encore la tête. Okba revient, engage la lutte mais il finit par succomber (685 de notre ère). Son tombeau se trouve dans l'oasis qui porte son nom à 15 kil. de Biskra. C'est un lieu de pèlerinage très fréquenté.

Un autre personnage non moins curieux, c'est la Kahena (nom juif, féminin de Kahen). Celle-ci reine, à caractère sacerdotal, d'une tribu berbère convertie au judaïsme, était forte comme un homme et courageuse comme un héros. Elle se lançait dans la mêlée, sans crainte du danger. Ses soldats suivaient et se battaient sans lâcher pied. Elle devint populaire. Hassan, chef des bandes arabes, battu une première fois par Kahena, groupa à nouveau ses forces et reprit l'offensive. La reine berbère vaincue et prisonnière fut décapitée.

A Baghaï, à 14 kilomètres au Nord de Khenchela, elle avait installé sa maison, son camp et son centre d'action.

Au XI^e siècle, se produisit avec une effroyable violence la deuxième invasion des arabes. Au XVI^e siècle, la domination turque s'étendait sur tout le pays ;