Необходимость укомплектовать свой экипаж заставила его на время помириться с тунисским султаном. Подъехав к самому городу, он написал к Мулей-Ахмеду, предлагая возвратить Бужию, некогда ему подчиненную и отнятую в 1510 году испанцами. Предложение это очень понравилось легковерному султану и было принято с радостью. В распоряжение Харуджи тотчас отданы два тунисских корабля и конвой со съестными припасами. Смелый пират явился в виду Бужии в начале 1514 года и высадился с 50 отборными турками для отыскания выгоднейшей точки атаки. Но испанцы направили на них пушку малого калибра, и судьбе угодно было, чтобы первое ядро попало в Харуджи и раздробило ему руку. Принужденный отказаться на время от своего намерения, он передал начальство Хеир-Эддину и едва не умер от ампутации. Впав в расслабление, заставлявшее опасаться за его жизнь, он не хотел возвратиться в Тунис и попросил своего брата отвезти его на берега Испании, где надеялся умереть в шуме последней битвы.
Мавры, изгнанные из Гранады и Альпухаррасских гор преследованиями Фердинанда Католика, распространили на всем африканском прибрежье весть о бедствиях своих собратий, и эта печальная картина с каждым годом принимала более и более мрачные оттенки. Оранские и алжирские корсары в каждую экспедицию привозили с собой новых беглецов, соединившихся с ними, и Хеир-Эддин был уверен, что крейсерство в водах Малаги доставит ему многочисленных партизанов, с нетерпением ожидающих освобождения во что бы ни стало от притеснений, которым подвергались, и жаждавших мести против своих утеснителен.
Прибыв к острову Минорке, где надеялся снабдить съестными припасами экипаж пяти кораблей, он нашел берег опустелым: жители убежали при его приближении. Хеир-Эддин с отборным отрядом сделал высадку, обыскал покинутые местечки и селения и прошел во внутренность острова до маленького увеселительного замка, окруженного великолепными садами. Как человек осторожный, он оставил часовых на близком пригорке, с которого с помощью сигналов, мог сообщаться с эскадрой, потом с тридцатью решительными разбойниками напал на замок, легко овладел им, разграбил и взял 40 пленных. Ободренный этим успехом, он намеревался пройти еще дальше, когда триста миноркцев, засевших в горах, вдруг мужественно напали на него. Несмотря на свою малочисленность, пираты выдержали напор и, сражаясь, отступили к кораблям. Едва достигнув их, Хеир-Эддин пишет к жителям угрожающее письмо: «Знайте, что я гром небесный и скоро явлюсь для уничтожения ваших имуществ, для предания жен и дочерей ваших моим воинам, для увлечения ваших детей в неволю!» Дав одному пленнику свободу, он отправил его с этим письмом на остров. Но слабость Харуджи не позволила исполнить угрозу и, терпя нужду в съестных припасах, он не поехал в Испанию, но, оставив Минорку, направил путь к Корсике, на которую наложил контрибуцию, и, ограбив несколько купеческих кораблей, принадлежавших разным нациям, возвратился на тунисский рейд с богатой добычей, лучшую часть которой поднес Мулей-Ахмеду взамен попечений, которых требовало положение его брата, несколько месяцев уже терзаемого медленной горячкой.
Весной 1515 года, Харуджи, совершенно излеченный, почувствовал в себе возвращение страсти к отдаленным экспедициям. На место отрезанной руки, хирурги приделали руку серебряную, которая двигалась посредством искусно рассчитанных пружин. Когда от купцов, посещавших тунисские базары, узнали в Европе о выздоровлении этого бича морей, ужас, возбуждаемый его именем, возобновился, но Харуджи задумал важнейшие планы, чем бродячую жизнь, которой предавался в продолжение десяти лет, его орлиный взор снова обратился на Бужию, которую он надеялся завоевать с помощью Мулей-Ахмеда, хотя решился оставить ее за собой в случае удачи.
Первым делом его было приобрести посредством богатых подарков союзничество одного могущественного предводителя горцев, живущих около Джиджели, по имени Бен-эль-Кади. Он уговорил его напасть со стороны земли с 1500 кебилами на Бужию, между тем, как эскадра пиратов нападет на укрепления с моря. Харуджи прибыл к городу с двенадцатью кораблями, высадил без помехи свой отряд, припасы, артиллерию и расположился на холме, господствующем над рейдом Первая атака его, направленная против старого арабского форта, имела счастливый результат, но новый замок, построенный и занятый с 1510 года испанцами, остановил его усилия: после нескольких бесполезных приступов, стоивших ему 300 человек, он благоразумно решился превратить осаду в блокаду, когда вдруг пять больших военных кораблей, приведенных из Алжира Махином де-Рентериа, за которыми вскоре последовали две небольшие эскадры с Майорки и из Валенсии, еще увеличили невыгоду его положения. Не испугавшись, однако, такого приращения неприятельских сил Харуджи удвоил усилия и начал день и ночь обстреливать новый замок, гарнизон которого отвечал сильным и хорошо поддерживаемым огнем, причем не забывали и кораблей христианских, которых положение его на возвышении удерживало от подания помощи крепости. Между тем, снаряды его истощались, а новый замок, защищаемый стенами, толщиной в несколько метров, стоял твердо. Осада длилась, и Харуджи начинал досадовать на свое бессилие. Несчастный случай довершил его неудовольствие: брата его, Исаака, управляющего артиллерией, на глазах его разорвало надвое пушечным ядром Смерть его причинила ему такую горесть, что, без просьб его союзника Бен-эль-Кади, Харуджи лишил бы себя жизни. Отказавшись от исполнения цели экспедиции, он отступил на берег Уэд-эль-Кебира, реки при Бужии, в извилинах которой спрятал свои пять кораблей, но здесь ожидало его новое бедствие: река почти совсем высохла от большой жары и эскадра его сидела на мели. Тогда Бен-эль-Кади предложил ему убежище в Джиджели, и Харуджи последовал за ним с 40 турками — единственным остатком от маленькой армии, которую он надеялся повести к легкой победе. В этом бедном селении, наконец, судьба отыскала морского разбойника, истощившего все свои средства и потерявшего почти всякую надежду, чтобы вдруг сделать его владыкой Алжира.
Смерть Фердинанда Католика, случившаяся 23 января 1516 года, возродила мужество мавров и алжирцы, наскучив быть данниками Испании, избрали своей главой шейха с равнины Метиджы, Селима Эйтеми, человека уважаемого за его богатство и древность рода. Селим принял власть, но не чувствовал в себе довольно смелости, чтобы прогнать испанцев из страшной цитадели, сооруженной ими на мысе, господствовавшем над городом. Доверчивый и легковерный, новый король предложил купить помощь Харуджи. В Джиджели отправили депутацию для объяснения знаменитому корсару унижения, в которое впал Алжир, и для представления ему, что смерть Фердинанда и дряхлость Хименеса надолго лишат Испанию возможности возобновить африканскую войну, следовательно, такому человеку, как он, будет легко прогнать гарнизон из Пеньона. К этому присоединили богатые подарки и предложение места алжирского губернатора.
Харуджи одним взглядом измерил шансы в будущем, которые могли привести его пламенное честолюбие, но, боясь подозрений, он скрыл свою радость и уступил наконец, по-видимому, только неохотно и после многократно возобновленных просьб. Сам Бен-эль-Кади, совета которого он спрашивал в этом деле, был обманут видимым равнодушием Харуджи, который поговаривал о желании окончить дни свои в уединении. Показывая вид, что уступает только настойчивым просьбам алжирских депутатов, Харуджи объявляет, что не в состоянии помочь им без помощи своего друга Бен-эль-Кади. Эта лесть очаровала начальника кебилов и он немедленно приказывает вооружить две галеры в Джиджели, а сам собирает около 500 горцев, чтобы сухим путем идти к Алжиру.
Итак, с сорока турками и горстью кебилов, Харуджи, сам того не зная, отправлялся завоевать царство, что должно было обессмертить имя его в истории и подчинить, в продолжение трех столетий, европейские прибрежья законам беспощадной тирании. Не уезжая еще из Джиджели, он отправил нарочного к Хеир-Эддину, остававшемуся в Тунисе, извещал о возврате счастья и просил привести ему в подкрепление сколько можно более решительных молодцов, которым обязывался платить ежемесячно значительное жалованье.
По прибытии в алжирскую гавань, о котором не узнал гарнизон Пеньона, он был принят народом и Селимом Эйтеми как освободитель, и последний предложил ему жилище в собственном доме. Жители, в свою очередь, спорили о чести поместить у себя и содержать бесплатно его турков. Харуджи растолковал им, что неосторожно открыть неприязненные действия против испанского форта прежде прибытия солдат, которых он ожидает из Туниса. Скоро в самом деле триста отборных турков, вооруженные ружьями и снабженные несколькими легкими пушками, высадились ночью у мыса Мати- фу и прошли в Алжир равниной. Отряд этот известил алжирцев о скором прибытии еще других отрядов, которые образовывались на всем прибрежьи при имени Харуджи, и через месяц пират увидел себя во главе значительных сил. По требованию его, Селим Эйтеми наложил на алжирцев особенную дань для содержания войска их союзника, и никто не осмеливался роптать, ибо все надеялись, что победа позволит отправить их восвояси, наградив за помощь по заслугам. Надо же было принести какую-нибудь жертву надежде на освобождение.
