Les relations vont se détériorer quand, vers 1519, Ahmed Belkadi prend position pour les troupes tunisiennes du roi Abou Abdallah, partie à la reconquête de l'Est algérien tombé sous la domination des Turcs. Les troupes tunisiennes, parvenues en Kabylie, étaient sur le point d'être battues par Kheïredine, quand Ahmed Belkadi fonce sur les Turcs, pris ainsi entre deux feux. Kheïredine, poursuivi par le Kabyle, se replie sur Alger. Abandonné par sa milice, Kheïredine s'enfuit à Djerba, laissant la place à son ennemi qui occupe la ville. Cet événement se situe, selon les historiens, entre 1520 et 1523. Saïd Boulifa, dans son Djurdjura à travers l'histoire, pense que l'occupation d'Alger par les Kabyles a duré sept années. Quoi qu'il en soit, les Algérois, incommodés par les troupes kabyles, finissent par rappeler Kheïredine. Certains auteurs font remonter le nom de Kouko à Gao, l'ancienne cité du Niger, autrefois centre commercial et intellectuel florissant de l'Afrique subsaharienne, arguant de relations entre cette cité et le royaume de Kouko mais cette étymologie ne fait pas l'unanimité. On ne voit pas, en effet, comment le nom de cette ville lointaine ait pu être donné à un village kabyle.
