The government of the Berbers was at this time exercised by Koceila, son of Lemezm, who had originally been a Christian, but who had become a Mohammedan during the first Arab invasion, and had returned to his ancient faith under the government of Abou el-Mohadjer. He rallied all the disaffected Berbers to his standard, but he was completely defeated by Abou el-Mohadjer, taken prisoner at Tlemçen and only escaped death by again making a profession of Islamism.

Okba ibn Nafa, who had returned to Africa to replace Abou el-Mohadjer, undertook the conquest of the Moghreb. He penetrated as far as the Atlantic, and received the submission of Count Julian, who governed Tingitana for the Goths of Spain. He retained Koceila in close captivity in his camp and treated him with the utmost indignity. He repossessed himself of the strong places, such as Baghai and Lambessa, and deposed all the Berber princes from their governments. On one occasion however, having sent the greater part of his army to Kerouan, and kept but a small detachment with himself, the tribe of Koceila, with whom their chief had always been in secret communication, profiting by his temporary weakness, fell upon him at Tahouda near Biskra, and killed both him and all his followers.[59]

Koceila fixed his residence at Kerouan, and governed the Berbers and Arabs with great justice and moderation during five years; but in the 67th year of the Hejira (A.D. 686-7) he was defeated by Zoheir ibn Keis el-Belowi, who had been sent by the Khalifa Abd-el-Melek to avenge the death of Okba, and was slain with a vast number of his followers. The remainder of the Berbers fled for security to their strong places and to the mountains.[60]

The Aures was at this time governed by a princess whose name was Dihya, daughter of Tabita, but who is more generally known by the appellation of El-Kahina, the sorceress; according to Ibn Khaldoun,[61] she professed the religion of the Jews, and her ordinary place of residence was at El-Baghai. By this time Zoheir had been killed and Hassan bin Näaman was sent against her. He was signally defeated and pursued by the victorious Kahina as far as the borders of Tripoli. During five years she continued to reign, with as much justice and clemency as her predecessor; but she was subsequently overcome, and she together with her principal nobles fell gloriously in battle, overwhelmed by the superior power of her Arab conquerors.

The very means which she took to arrest the progress of her enemies predisposed the minds of her people against her, and contributed to her downfall. She destroyed all the towns and farms in which the Arabs could obtain shelter, and burnt those magnificent forests, which made the whole country between Tripoli and Tangier one continuous garden. This would naturally have been put down as an exaggeration or mere tradition, but for the chain of Roman ruins still existing to prove how richly cultivated and how densely peopled the country once was, much of which is now all but desert.

The story of El-Kahina is just such a one as the Arabs love to build their romances on. A local tradition is recorded by Commandant de Bosredon.[62] This part of the country was formerly under the rule of a great chief called Aures, whose wife’s name was Khenchla. This powerful family had several castles, the ruins of which are still existing at Daharet-Foua, Bahiret-Sebkha and Khenchla, his usual place of residence. The daughter of Aures, known generally by her pseudonym of El-Kahina, was a person of great beauty and high intelligence. She had received a brilliant education under the direction of her father, and one corresponding to the distinguished rank she occupied. When of age to be married, her father left her free to select her own husband. Amongst the numerous aspirants for her hand, El-Kahina chose Berzegan, whose name is perpetuated in the great ruins situated to the south of the Ma el-Abiad. The marriage act was drawn out, but Aures died before the ceremony could be accomplished.

The successor of Aures was one of those whose addresses El-Kahina had rejected, and who on this account meditated a project of vengeance. Being a man of an evil nature, he abused his power to commit the most infamous actions. Amongst other customs, he introduced one formerly claimed by feudal lords in Europe, and as El-Kahina refused to submit to this indignity, she delayed for some time her marriage. At last, heartsore at seeing the whole nation victims of this unworthy prince, she determined to effect the liberation of her country. She invited some of the bravest youths of her family and acquaintance to a banquet, at the termination of which she made known to them her projects, which met with universal approbation. She then made the necessary preparations for her marriage, and according to the recently established custom, she proceeded with her companions to the residence of the sovereign. She penetrated alone into his apartments, and having in vain endeavoured to divert him from his evil way, she plunged a poignard in his heart, and was hailed as his successor.

Thus we have seen one invasion after another sweep over the country, and always with the same effect—the conquerors, after a short lapse of time, became in their turn the conquered, and were driven for safety to the mountains.

Ibn Khaldoun remarked of the Berbers, that they held the first place amongst nations for bravery and promptness to defend their guests, for fidelity to their engagements, patience in adversity, hospitality and many other great qualities.[63]

This reputation, no doubt, induced the persecuted Latins, and even the Vandals, to seek the shelter of these peaceful retreats, where they soon became assimilated to the aboriginal Berber race. The result is, that these northern nations have left on the Chawia the imprint of their physical and moral character in a way that fourteen centuries have not been able to obliterate.