Между тем, как сын его подвергался поражению, Сала-Реис, предводительствуя сорока галионами и бригантинами, отмщая на христианах неудачи свои против арабских племен 5 июля 1553 года взял близ Гибралтара часть португальских кораблей, только что вошедших в Велезский порт. На этой эскадре везли войска в мароккские владения, чтобы возвратить Мулей-бен-Азуну престол Феца, с которого согнали его. Мавританский принц находился на одном из этих кораблей. Сала-Реис укорил его в том, что он преступил правила своей веры, предпочтя помощь христиан помощи турков, потом отвез его в Алжир и условился с ним насчет экспедиции против Феца. Несмотря на поражение в восточных горах, он сумел выставить перед ним в блестящем свете удовольствия и выгоды отдаленного похода. Арабы равнины поспешили выставить многочисленное вспомогательное войско, и сами кебилы, забыв, что поразили турков, согласились соединиться с ними для участия в богатой добыче. Бен-эль-Кади, шейх Кусы, которого тревожило могущество Абд-эль-Азиза, присоединился к паше с 3000 всадников. Приготовления к войне заняли всю осень 1553 года. В первых числах января 1554 года Сала-Реис выступил из Алжира с 11000 пешими и конными воинами и 12 пушками. В то же время флот в 82 судна получил приказание идти к Мелиллаху, нагруженный съестными припасами, военными снарядами, подкреплениями, готовый поддержать его, или, в случае неудачи, доставить ему безопасное убежище. Но паша без препятствий дошел до стен Феца, сразился с шерифом, истребил его войско и вступил в город, который совершенно разрушил. После этой победы, весть о которой быстро пронеслась по всему Могребу, он удовольствовался тем, что потребовал от Мулей-бен-Азуна уплаты военных издержек и подарков для себя и своих офицеров. Алжирский флот, между тем, овладел фортом Мелиллах, выстроенным на скале в почти неприступной позиции, но худо оберегаемом. По приказанию паши, в нем оставили 200 янычар.
Возвращаясь из Феца, Сала-Реис прошел через Тлемсен, Мостаганем и Тенес и принял все меры для обеспечения спокойствия страны. Едва вернувшись в Алжир, он решился завоевать Бужию на восточном берегу, которой владели испанцы. Три тысячи турков атаковали город со стороны моря в первых числах июня 1555 года, между тем, как 30'000 арабов направлялись к нему с равнины. После двадцатидвухдневной упорной обороны, христианский гарнизон, видя укрепления разрушенными и истощив все съестные припасы, предложил капитуляцию с воинскими почестями. Желая кончить осаду, Сала-Реис согласился на условия, предложенные храбрыми воинами, доведенными до крайности, но потом велел окружить их, обезоружить и отвести в неволю. Один комендант получил свободу и уехал в Испанию, выйдя на берег, он был схвачен по повелению Карла V, предан военному суду и казнен на Валльядолидской площади, — наказание, которого не оправдает никогда горесть, какую причинила испанскому государю потеря Бужии.
Сардинский ренегат Али остался в этом городе с 400 турками, а Сала-Реис возвратился в Алжир со 120 женщинами, из которых красивейшие населили его гарем, а прочие проданы на торжище.
Эти быстрые успехи побудили пашу изгнать испанцев из Орана и Мерс-эль-Кебира, последних убежищ их на алжирском берегу. Со времени появления турков на этом берегу, покоренном в несколько дней Петром Наваррским, Карл V владел на нем уже только двумя крайними пунктами — Тунисом на востоке и Ораном на западе. Но Оран был хорошо укреплен, близок к Испании и способен противопоставить повторным попыткам долгую оборону. Сала-Реис, не полагаясь на одни свои силы, отправил сына своего Мухаммеда в Константинополь для донесения Сулейману о взятии Бужии и испрошения помощи для дальнейших завоеваний. Султан немедленно послал ему 6000 турков и 40 галер.
Предуведомленный о скором прибытии этих подкреплений, смелый пират вышел в море в июне 1556 года с 30 кораблями, и остановился ждать отоманский флот у мыса Матифу, но, внезапно пораженный чумой, умер через несколько часов, семидесяти лет от роду. Турецкая армия похоронила его великолепно и соорудила ему блестящий мавзолей близ ворот Баб-эль-Уэд.
В ожидании начальника, которого назначит Сулейман, алжирский гарнизон вручил верховную власть корсиканскому ренегату Гасцену, который принял тотчас начальство над экспедицией, остановленной смертью Сада-Рейса. 3000 турков, 14'000 мавров и 20'000 арабов и кебилов качали осаду Орана и уже башня Святых, построенная за городом для защиты источников, пала под ядрами, когда прибыл корабль из Константинополя с запрещением продолжать осаду и с приказанием турецкой эскадре вернуться. Смерть Сала-Реиса заставила Сулеймана отсрочить исполнение этого важного предприятия. В следующем сентябре месяце назначен пашой турок по имени Текели: это известие произвело возмущение. Янычары любили Гасцена и не хотели принять его преемника. Текели, явившись перед Боною и Бужией, был встречен пушечными выстрелами, а Алжир не отвечал на его сигналы. Однако же, соперничество интересов между янычарами и настоящими пиратами вскоре прекратило такое положение дел. Янычары составляли милицию привилегированную и на жалованьи, воинская организация делала их обладателями гаваней, тогда как пираты, живя единственно добычей, придерживались твердой земли только как безопасного складочного места награбленному. Янычары, завидуя богатству пиратов, не раз просили быть принятыми на корсарские корабли, но начальники последних всегда отказывали им. Следствием этого была неприязнь, давно царствовавшая между теми и другими. Пираты, которым было все равно, какому паше ни повиноваться, опасаясь при том гнева султана, если будут участвовать в возмущении янычар, решились втайне пропустить Текели в Алжир. Чтобы успеть в этом, они показывали вид, что соединяются с милицией, и в качестве моряков требовали, чтобы им было вверено охранение гавани. Успев в этом, они представили, что надобно требовать немедленного удаления Текели от берегов алжирских: и это предложение принято единогласно. Халог, начальник рейсов, взял на себя исполнение этого поручения, сел на свою бригантину, поехал к мысу Матифу, бросил там якорь, и вступил в сношения с Текели. Новый паша, извещенный о заговоре пиратов, ночью пересел на галеру Халога с двадцатью отборными воинами, приказав эскадре из восьми галер, его сопровождавшей, следовать за ним в недальнем расстоянии. Приехав, он высадился с помощью ночного мрака, принял начальство над пиратами, собравшимися в гавани, и тихонько пробрался в город. По прибытии его к дворцу нашей, к нему присоединились солдаты с эскадры и все громогласно приветствовали Текели. Янычары, вскочив спросонок, бросились к оружию, но при виде солдат, наполняющих улицы, они догадались об измене пиратов и заперлись в домах своих. Гасцен-Корсиканец, услышав шум, вышел из дворца, явился к новому губернатору, уверял его, что нисколько не участвовал в возмущении и что янычары силой принудили его принять начальство над ними. Текели, не слушая этих оправданий, приказал связать его и бросить в тюрьму. Та же мера была принята против губернаторов Бужии и Боны. Неделю спустя, начальник первой, Али-Сардинец, привезен в Алжир, другой, укрывшийся в Тунисе, был схвачен позже. Гасцен-Корсиканец, приговоренный к смерти, живой брошен на железные крючья Баб-Азунских ворот, и умер после трехдневных неслыханных страданий. Али-Сардинцу, приведенному туда же, надели раскаленную каску и потом посадили его на кол.
Эти отвратительные жестокости и грозное положение, принятое Текели, возбудили неудовольствие милиции. Один калабрийский ренегат, Юссеф, бей тлемсенский и друг Гасцена, поклялся отомстить за его смерть и сделался душою нового заговора. Уверенный в содействии алжирских янычар, он смело водрузил знамя мятежа и с отборным отрядом пошел против Текели. Преданные лазутчики уведомили его, что паша, опасаясь чумы, удалился в загородный дом на морском берегу. Он поспешил туда и напал на него: Текели едва имел время сесть на коня и во весь опор поскакал через сады в город, но янычары заперли ворота и Юссеф, преследуя его, догнал у местного марабута и проколол копьем, упрекая его в смерти Гасцена. После этого подвига, совершенного в последних числах декабря 1556 года, Юссефа впустили в Алжир, и турецкая милиция подняла его на щиты, как спасителя. Но эта удача была непродолжительна: Юссеф погиб от чумы, и янычар Агиа, преемник его, не дерзнул, полгода спустя, бороться с Гассан-Пашою, сыном Хеир-Эддина, восстановленным султаном в Алжирском пашалыке, куда он прибыл с шестью галерами.
Прибытие законного владыки немедленно ознаменовалось новыми подвигами. Шериф Феца осаждает Тлемсен; Гассан-Паша делает воззвание к арабам, которые выставляют 16'000 человек, присоединяет к ним 2000 турков и летит с ними на выручку города. Шериф отступает, он преследует его до окрестностей Феца и вступает в кровопролитное сражение, продолжающееся до вечера, но выгода остается на стороне мавров. Турецкое войско ночью снимает лагерь и возвращается на мелиллахский берег, где ждала его резервная эскадра, для отвоза в Мостаганем.
