One of the most famous of ancient legendary figures among the Amazigh is Dehia, called the Kahina (seer, priestess), a label said to have originated with the Arabs, against whom she led her army. However, the name of "Kahina" most likely derived from the ancient Jewish priestly class (KHN, found in names like Cohen, Khan, etc.). Unlike most women of medieval history, she achieved greatness through her own efforts. A self-made woman, her power was not owed to a husband, lover, or inheritance.

According to some accounts, including that of the fame writer and early historian, Ibn Khaldoun, Dehia was a Jewess. However, this is not proven and is disputed among scholars, though the very label of Kahina seems to give credence to this particular story. Moreover, it is traditionally accepted among the Imazighen themselves that she was Jewish, including in the Aures region, from which she hailed, according to Ibn Khaldoun's account. Some tales concerning the female warrior recount that her people were relative newcomers; others state they were descendants of the Jews, who had fled into the region to escape the Romans during the Cyrene massacres of the second century.

Dehia's career began when she took charge of the Amazigh army after Koceila, who had battled and been victorious over the Muslim invading army led by Okba. According to several histories, Dehia may have taken over at a very advanced age. When she was still young, she had freed her people from a cruel and tyranical local leader, whom she agreed to marry, then murdered on their wedding night. Her love life after this particular event is not known other than she gave birth to three sons, each probably fathered by different men.

Ibn Khaldoun states that she possessed the gift of prophecy and "never failed" to correctly foretell the future. Because of her gift, probably a result of her intelligence and persuasive manner, she became queen of her tribe, and later, of all the Imazighen of the region.

Dehia became the fiercest opponent of the invading Arab-led armies, but finally, realizing that her people were too weak to fight the invaders indefinitely, she decided that the only way to force them to leave was to give them no reason to want to stay. She had the countryside burned and sacked to impoverish the area and remove its beauty, thus making it undesirable. This decision did not affect her mountain people much, but the rest of the population was angry. She began to lose her power.

Instead of discouraging the Arab armies, her desperate decision hastened defeat. According to some accounts, she died fighting the invaders, sword in hand, a warrior's death (other accounts say she committed suicide rather than be taken by the enemy). This was around 693 AD, when she was, according to ancient accounts quoted by Ibn Khaldoun, "127 years old." This was probably not meant literally. Great age was often depicted with exaggerated numbers, as is also found in the Torah (Old Testament to the Christians). Legend also has it that she was beautiful and passionate to the end.