Arouj multiplie les exploits, s'emparant de navires espagnols et faisant des prisonniers parmi les gentilshommes qu'il rançonne. Au cours de ses expéditions, Arouj ne se contente pas d'attaquer les bateaux ennemis, il va aussi faire passer, d'Espagne au Maghreb, des milliers de musulmans restés sur place après la reconquête et pour lesquels la vie était devenue impossible. Cependant, les Espagnols, s'étant emparés de plusieurs villes côtières algériennes, s'attaquent, en 1510, à Béjaïa. La ville leur a déjà résisté à plusieurs reprises et même infligé des pertes aux envahisseurs, mais cette fois-ci, les Espagnols sont plus nombreux et surtout mieux armés. Le sultan Abderrahmane El-Hafsi, après avoir essayé de résister à l'invasion, s'enfuit dans les montagnes de la vallée de la Soummam, parmi les populations kabyles qui l'accueillent. Les Espagnols vont chasser toute la population de la ville et la remplacer par des chrétiens de Malaga. C'est en apprenant les succès de Arouj, que le roi l'appelle au secours. «Un musulman, lui fait-il dire, ne peut laisser des musulmans se faire ainsi chasser de leur ville, il ne peut laisser sa maison plus longtemps occupée par l'ennemi ni ses mosquées transformées en églises !»
