Haëdo nous apprend, dans son Histoire des rois d'Alger, que de passage à Mytilène, Baba Aroudj apprend la mort de son père. Ses deux frères cadets, Kheyr-din et Ish'aq, qui vivent dans la misère, le supplient de les prendre avec lui et lui avouent que sans lui, ils seraient perdus. Ils les emmènent et voici les trois frères Barberousse unis pour le meilleur et pour le pire. En 1504, il arrive à La Goulette, en Tunisie. Le sultan hafside de Tunis l'accueille favorablement, l'autorise à entrer dans ses ports et, plus tard, il lui offrira même le gouvernement de l'île de Gelves (Djerba) qui servira de base à sa flotte. L'un des premiers succès de Arouj au Maghreb a été la prise de deux navires appartenant au pape Jules II. Les deux galères venaient de Gênes et se rendaient à Civita-Vecchia. Caché dans les eaux de l'île d'Elbe, un des navires s'étant écarté de l'autre, il l'attaque et le prend sans difficulté. Puis, pour tromper la vigilance de l'autre bateau, il fait enlever à ses captifs leurs vêtements et les fait revêtir par ses hommes, il accroche aussi la banière du pape à son mât. Le bateau ne se doute de rien, en voyant approcher Arouj et quand il comprend enfin à qui il a affaire, c'est trop tard ! Il est attaqué et pillé.
