Сын Хеир-Эддина был столь же ловкий политик, как хороший воин. Убедившись из примера Эль-Хаджи-Мехеми в непостоянстве турецкой милиции, он понял, что не должен вверять свою безопасность прихотям буйной шайки, но опереть свое могущество на выгодных договорах и союзах с арабскими племенами.

На восток от Алжира, на оконечности Метиджи, равнина начинает подыматься и мало-помалу соединяется с главной цепью Атласа. Эта гористая страна, труднодоступная, всегда была обитаема независимым и гордым племенем, не подчинявшимся никакому игу. Два города Кусо и Эль-Кала, существующие доныне, соседственные, но враждебные, в XVI столетии составляли две маленькие столицы, владетели которых вели между собой беспрерывную войну за разные дрязги. Кроме того, владетель Кусо, Бен-эль-Кади, питал к туркам глубокую ненависть со времени смерти своего родственника, Селима-Эйтеми, погибшего от руки Харуджи-Барберуссы в 1516 году. Абд-Эль-Азиз, шейх Эль-Кала, надеялся погубить посредством этого положения своего противника и тайком вступил с Гассан-Пашою в переговоры, губернатор Алжира не преминул извлечь пользу из корыстных видов горского предводителя.

В 1550 году тлемсенские мавры, не могшие более сносить ига Мулей-Ахмеда, истощавшего их непомерными налогами для удовлетворения ненасытимой жадности испанцев, написали в Фец, в Мароккской империи, предлагая власть брату тамошнего султана, но фецский шериф перехватил их послание и тотчас составил план для овладения Тлемсеном. Движение 10 000 марокканцев, быстро приближавшихся, заставило Мулей-Ахмеда снова покинуть свою столицу и спрятаться в Оране, между тем, как неприятель, победив его без боя и желая увеличить успехи свои, направился к Мостаганему, откуда рассчитывал пройти в скором времени и до Алжира.

Гассан-Паша, уведомленный заблаговременно об этом страшном вторжении, тотчас собрал отборнейших турков и потребовал помощи Абд-эль-Азиза, который поспешил под его знамена. Один корсиканский ренегат, Гасцен, принял начальство над алжирским войском. У него были два лейтенанта: турок, по имени Саффа, и сардинский ренегат, Али. Начальник марокканского войска, Абд-эль-Кадер, пораженный паническим страхом и не смея поджидать противников, отступил, гоня перед собою бесчисленное множество скота всякого рода и везя с собой разную добычу, отнятую у арабских племен. Но, настигнутый на переправе через одну реку, разлившуюся от дождей, что делало переход опасным, он обернулся, предпочитая шансы битвы почти верной гибели своей армии в волнах. Корсиканец Гасцен, в свою очередь, испугавшись отчаянной решимости Абд-эль-Кадера, медлил с атакой, но вдруг Абд-эль-Азиз, упрекая его в трусости, напал на неприятеля со своими варварийцами и кебилами и увлек за собой турков. После чудес храбрости и переменчивого счастья, поле битвы осталось за алжирцами. Сам Абд-эль-Кадер пал от ударов Абд-эль-Азиза, и победоносное войско в тот же день вступило в Тлемсен, который подвергся всем ужасным последствиям приступа. Турок Саффа был назначен губернатором, и ему оставили гарнизон в 1500 человек с десятью пушками и изобильными снарядами. Вот начало тлемсенского бейлика, перешедшего с тех пор под власть пашей. Турецкая армия, отдохнув несколько дней, возвратилась в Алжир, неся с торжеством голову Абд-эль-Кадера, воткнутую на пику. Трофей этот был заперт в железный ящик и повешен на своде Баб-Азунских ворот, где пробыл до 1573 года.

Вскоре после этого события Гассан-Паша был отозван в Константинополь для защиты важных личных интересов. Один племянник султана пожелал овладеть имением, оставшимся после Хеир-Эддина и, между прочим, заведением общественных бань, приносившим большой доход. Для достижения этого, он затеял интриги, которые должны были низвергнуть Гассан-Пашу. Алжирский губернатор, принужденный встретить угрожавший ему удар, вызвал бея Саффу из Тлемсена, поручил ему управление Алжиром во время своего отсутствия и 22 сентября 1551 года уехал в Константинополь с эскадрой из 6 кораблей. Но поездка его была неудачна: когда он приехал, враги его уже торжествовали, и Сулейман фирманом назначил в Африку нового пашу, имя которого мы встречали уже в числе товарищей Хеир-Эддина Барберуссы – то был Сала-Реис.

Новый сановник пошел по следам Гассан-Паши. Первой заботой его было возобновить с восточными кебилами и арабами равнины переговоры, чтобы в случае нужды обеспечить себе их помощь против возмущения, или употребить их для исполнения своих замыслов. Первая экспедиция его имела целью покорение шейха Тугурта, во сто милях от Алжира, на пределах Сахарской пустыни. После двадцатидневного похода он обложил Тугурт, открыл брешь, взял город штурмом, перерезал жителей, отказавшихся платить ему дань, а начальника их приказал привязать к жерлу заряженной пушки, выстрел которой разорвал несчастного на мелкие части. Из Тугурта победитель пошел в Уаргла, который нашел оставленным жителями, за исключением сорока торговцев неграми. Наложив на них контрибуцию в 200 000 золотых экю, и оставив в обоих городах гарнизон, он возвратился в Алжир. Но победа эта, вместо приобретения ему дружбы арабов, возбудила их зависть. Абд-эль-Азиз отказался идти под его начальством, по возврате из армии Сала-Рейса, он имел неосторожность быть в Алжире и едва не был схвачен и скован по приказанию паши: насилу успел он сесть на коня и ускакать в горы, чтобы приготовиться к защите. Этот сигнал к восстанию мог иметь на арабов пагубное влияние, безнаказанность Абд-эль-Азиза могла сделаться в глазах соседних с Алжиром племен воззванием к независимости. Нельзя было медлить уничтожением восстания в самом зародыше его. Сала-Реис тотчас выступил против Эль-Кала, но снега остановили его у подошвы гор и принудили отступить. Абд-эль-Азиз воспользовался этим для сооружения укреплений в ущельях и исправления цитадели. Кебильские племена всей страны, свидетели его мужества, забыли взаимные распри, чтобы соединиться против общего врага. Несколько месяцев спустя, второй отряд в 1500 турков и 6000 арабов, под предводительством Мухаммед-Бея, сына Сала-Рейса, направился опять к кебильским горам, прошел несколько линий ретраншаментов, которые неприятель покидал после слабой обороны, и подошел за милю от Эль-Кала – тут-то поджидали его горцы. Завязалась отчаянная битва, обе стороны понесли значительные потери, но знание местности поддерживало мужество кебилов, и турецкие войска, окруженные со всех сторон, только с неимоверными усилиями пробились назад на равнину.

Между тем, как сын его подвергался поражению, Сала-Реис, предводительствуя сорока галионами и бригантинами, отмщая на христианах неудачи свои против арабских племен 5 июля 1553 года взял близ Гибралтара часть португальских кораблей, только что вошедших в Велезский порт. На этой эскадре везли войска в мароккские владения, чтобы возвратить Мулей-бен-Азуну престол Феца, с которого согнали его. Мавританский принц находился на одном из этих кораблей. Сала-Реис укорил его в том, что он преступил правила своей веры, предпочтя помощь христиан помощи турков, потом отвез его в Алжир и условился с ним насчет экспедиции против Феца. Несмотря на поражение в восточных горах, он сумел выставить перед ним в блестящем свете удовольствия и выгоды отдаленного похода. Арабы равнины поспешили выставить многочисленное вспомогательное войско, и сами кебилы, забыв, что поразили турков, согласились соединиться с ними для участия в богатой добыче. Бен-эль-Кади, шейх Кусы, которого тревожило могущество Абд-эль-Азиза, присоединился к паше с 3000 всадников. Приготовления к войне заняли всю осень 1553 года. В первых числах января 1554 года Сала-Реис выступил из Алжира с 11000 пешими и конными воинами и 12 пушками. В то же время флот в 82 судна получил приказание идти к Мелиллаху, нагруженный съестными припасами, военными снарядами, подкреплениями, готовый поддержать его, или, в случае неудачи, доставить ему безопасное убежище. Но паша без препятствий дошел до стен Феца, сразился с шерифом, истребил его войско и вступил в город, который совершенно разрушил. После этой победы, весть о которой быстро пронеслась по всему Могребу, он удовольствовался тем, что потребовал от Мулей-бен-Азуна уплаты военных издержек и подарков для себя и своих офицеров. Алжирский флот, между тем, овладел фортом Мелиллах, выстроенным на скале в почти неприступной позиции, но худо оберегаемом. По приказанию паши, в нем оставили 200 янычар.