The early history of the Lak people is unclear; however, as noted above, they have lived in Daghestan since at least the Bronze Age. Although Christianity had been introduced by Armenians and Georgians starting in the sixth century, in 777, according to legend, the Laks were conquered by the Arabs under the leadership of Abu-Muslim. Islam was introduced among the Laks at that time, making them reputedly the first people of Daghestan to encounter Islam. The final conversion probably took place in the thirteenth century, with some pagan and Christian traditions surviving until the fifteenth century. According to legend, Shah Baala was the first Muslim ruler of all of Daghestan; he was the founder of the Shamkhal dynasty, which reigned at Kumukh until the seventeenth century. He renamed the village of Kumukh "Kazikumukh" (Qazi Kumukh or Ghazi Kumukh). In the fourteenth century the rulers of Kazikumukh adopted the title "shamkhal" (supposedly derived from "Sham," meaning Syria, suggesting descent from former Arab rulers). During the fifteenth and sixteenth centuries, at the time when the Shamkhals ruled a large part of central and coastal Daghestan, a second capital, which also served as a winter residence, was established at Tarku (Tarqu) in the Kumyk (Qumuq) territory. In 1640 the Laks broke away from the rule of the shamkhalate, replacing it with appointed khakhlavai (from the Arabic khalq, "people," and the Lak lavai, "supreme"). With the death of the last Kazikumukh khan, Agalar, the Lak territory was formally incorporated into the Russian Empire. In 1842 the Laks joined the Muslim rebellion in the northern Caucasus led by Sheikh Shamil and his Murids. This movement was aimed against both Russian (czarist, Christian) rule and the feudal aristocracy of the Caucasus that served what were perceived as Russian interests. The native Daghestani (including the Lak) aristocracy was deposed. At this time there was also a significant Sufi (Naqshbandiyah) movement taking place in Daghestan aimed at removing all pre-Islamic holdovers in the religious practices of the people. In 1877 another revolt took place against czarist rule. It was put down, resulting in further integration of Daghestan into the Russian Empire. During the Russian civil war, between 1918 and 1922, many Laks took part in yet another Islamic uprising in the northern Caucasus, this time against the Bolshevik regime.