Эти отвратительные жестокости и грозное положение, принятое Текели, возбудили неудовольствие милиции. Один калабрийский ренегат, Юссеф, бей тлемсенский и друг Гасцена, поклялся отомстить за его смерть и сделался душою нового заговора. Уверенный в содействии алжирских янычар, он смело водрузил знамя мятежа и с отборным отрядом пошел против Текели. Преданные лазутчики уведомили его, что паша, опасаясь чумы, удалился в загородный дом на морском берегу. Он поспешил туда и напал на него: Текели едва имел время сесть на коня и во весь опор поскакал через сады в город, но янычары заперли ворота и Юссеф, преследуя его, догнал у местного марабута и проколол копьем, упрекая его в смерти Гасцена. После этого подвига, совершенного в последних числах декабря 1556 года, Юссефа впустили в Алжир, и турецкая милиция подняла его на щиты, как спасителя. Но эта удача была непродолжительна: Юссеф погиб от чумы, и янычар Агиа, преемник его, не дерзнул, полгода спустя, бороться с Гассан-Пашою, сыном Хеир-Эддина, восстановленным султаном в Алжирском пашалыке, куда он прибыл с шестью галерами.
Прибытие законного владыки немедленно ознаменовалось новыми подвигами. Шериф Феца осаждает Тлемсен; Гассан-Паша делает воззвание к арабам, которые выставляют 16'000 человек, присоединяет к ним 2000 турков и летит с ними на выручку города. Шериф отступает, он преследует его до окрестностей Феца и вступает в кровопролитное сражение, продолжающееся до вечера, но выгода остается на стороне мавров. Турецкое войско ночью снимает лагерь и возвращается на мелиллахский берег, где ждала его резервная эскадра, для отвоза в Мостаганем.
Этот город, первый раз осажденный в 1547 году графом Алкодеттою, готовился быть целью новой атаки испанцев, опасавшихся близости турков и их замыслов против Орана и Мерс-эль-Кебира. Обладание Мостаганемом доставляло алжирским пиратам удобную гавань для складки части своей добычи. Поэтому необходимо было избавиться от таких опасных соседей, и граф Алкодетта только и мечтал о славе успеха в этом предприятии.
В первых числах августа 1558 года он выступил с 6000 свежего войска, присланного из Испании, и четырьмя маленькими пушками, везомыми солдатами. Желая обмануть неприятеля, он сначала пошел по противоположному Мостаганему направлению, и, проходив таким образом четыре дня, вдруг обернулся на Мазагран. Но турки давно уже были предуведомлены о его приготовлениях и движении. Арабские племена, чуя добычу, собрались, и граф Алкодетта, терпя недостаток в съестных припасах и в ядрах, принужден был остановиться на берегу морском после первой упорной стычки. Четыре галеры должны были подвезти ему к Мостаганему запасы всех родов. Каковы же были его удивление и отчаяние, когда они вдруг, в глазах его, были взяты пятью алжирскими кораблями! Встревоженный донельзя положением, в котором оставляло его это приключение, он собрал военный совет. Мнения разделились: одни советовали вернуться в Оран, другие, и в большем числе, требовали немедленного штурма Мостаганема, взятие которого должно было доставить им все, в чем нуждались они. Граф Алкодетта принял последнее мнение. Несколько солдат сработали тринадцать ядер и привесили их к седлам. Конечно, этого было слишком мало, чтобы пробить брешь, но губернатор Орана не мог перенести мысли о постыдном отступлении, и притом несчастная звезда увлекала его.
Солдаты, понимая неминуемую гибель, от которой мог спасти их только необыкновенный и непредвиденный случай, действовали слабо и были отражены без труда. Напрасно граф собственным примером старался возвратить их в битву: никто больше не слушал его, и в это самое время прибытие турков из Алжира, предводимых Гассан-Пашою, докончило поражение, которого Алкодетта не хотел пережить: он бросился навстречу трусливых солдат своих, которые переехали через него в безумном бегстве и оставили его на поле, истоптанного лошадьми. Гассан-Паша пожалел о его кончине и выдал тело за 2000 червонцев, но, негодуя на малодушие испанцев, приказал изрубить в этот несчастный день (26 августа 1558 года) более 800 пленных.
За этими отдаленными экспедициями вскоре последовало возобновление вражды с горными племенами на восток от Алжира. Абд-эль-Азиз, шейх Эль-Кала, начал снова набеги на турецкую территорию и налагал дань на племена, отказывавшиеся от вступления с ним в союз. Его влияние и успехи всюду распространяли ужас, он сумел привлечь к себе множество из тех ренегатов, которые в алжирской милиции составляли страшный корпус стрелков. Дезертирование, поощряемое его обещаниями, ежедневно приводило в ряды его войска новых союзников и, при помощи искусного расположения войск, он время от времени одерживал значительный верх над турецкими солдатами. После победы при Мостаганеме, Гассан-Паша решился жестоко наказать кебилов. В сентябре 1559 года с отрядом в 18 000 человек, в числе которых находились все христианские пленники из алжирских тюрем, которым была обещана свобода за их услуги, он выступил из Алжира. Кампания эта, в стране почти неизвестной и трудно доступной, тянулась, а решительных сражений не было. Паша, потеряв бодрость от неуспеха, кончил войну предложением мирного договора, который должна была скрепить женитьба его на дочери Абд-эль-Азиза, но шейх с презрением отверг предложение противника, не смогшего победить его. Гассан-Паша целый год скрывал свою досаду и, пользуясь этим временем, заключил союз с шейхом Кусы, Бен-эль-Кади, и женился на дочери его. Бен-эль-Кади не мог найти удобнейшего случая к увеличению своего могущества насчет соперника и доставил Гассану 1500 пехотинцев, вооруженных мушкетами, и триста всадников. После нескольких стычек, Абд-эль-Азиз, сжатый между двумя неприятелями, предложил мир, на который согласились безусловно. Однако тесная дружба Гассан-Паши с Бен-эль-Кади вскоре возбудила подозрения алжирских янычар, и союз этот, который в благоустроенном государстве способствовал бы к утверждению владычества Алжира в горах, где его никогда не признавали, возбудил здесь возмущение милиции. Турки не позволяли кебилам и арабам покупать огнестрельное оружие. Гассан-Паша, отступая в первый раз от такой благоразумной меры, снял это запрещение и дозволил горцам Кусы снабжать себя в Алжире всяким наступательным и оборонительным оружием, в котором могли нуждаться. Итак, это племя, без того могущественное и богатое, само изготовлявшее порох и ружья, должно было сделаться еще страшнее, и, если оставалось верным туркам, могло открыть им горные дефилеи. Но янычары стали подозрительны, видя такие необыкновенные поступки Гассан-Паши, они начали опасаться, не замышляет ли он чего-нибудь против них самих и не намерен ли, с помощью кебилов, сделаться независимым, отказаться от подчиненности Порте и изгнать турков. Ага янычар созвал в своем доме тайное совещание, в котором было решено низвергнуть Гассана Несколько дней спустя, в начале октября 1561 года, сын Хеир-Эддина был схвачен в своем дворце, закован в цепи и отведен на корабль, который должен был отвезти его к ногам султана, как изменника. При всем том, однако, турецкая милиция не осмеливалась назначить преемника изгнанному повелителю и удовольствовалась дать are временное звание халифа Но Гассан-Паша без труда убедил султана в совершенной невинности своей и был отвезен обратно в Алжир на сильном флоте, начальник которого приказал схватить агу янычар и отрубить ему голову.
Ограничив месть свою этой казнью, паша вступил снова в управление, не показывая никакой злобы против тех, которые изменили ему. Будучи ловчее бешеного Текели, он решился отделаться от своих врагов так, чтобы никто не мог обвинить его в жестокости: оранская экспедиция представляла ему к тому удобнейшее средство. Тридцать пять кораблей, на которые было посажено 15'000 человек войска и конвой с припасами всякого рода, получили приказание крейсеровать в водах Арзева, между тем, как 3 апреля 1563 года Гассан выступил сухим путем
Дон Альфонс Кордовский, сын графа Алкодетты, командовал Оранским гарнизоном. Турецкая армия расположилась недалеко от башни Святых, которую взяла после непродолжительного сопротивления, потом Гассан-Паша, флот которого занял гавань Мерс-эль-Кебира, отрядил часть своего войска к форту Св. Михаила, защищавшему город со стороны земли. Здесь ожидало его отчаянное сопротивление. Парламентер, приглашавший испанцев сдаться на капитуляцию, был убит из аркебузы. Разгневанный этим, паша приказывает идти на приступ, не дожидаясь даже, пока артиллерия флота пробьет брешь. После сильного напора турки отбиты; лестницы, приставленные ими к стенам, опрокинуты испанскими солдатами, мужество которых усиливалось сознанием, что им не будет пощады, и более 500 янычар лишились жизни в этой бесплодной попытке. Гассан-Паша втайне радовался этой неудаче, освобождавшей его от значительной части личных врагов, которым, под предлогом отличить их, он назначил самые опасные посты, и, нисколько не тревожась об успехе экспедиции, он окружил себя укрепленным лагерем, приказал свезти на берег пушки и 4 мая открыл огонь, который разрушил часть стен форта Св. Михаила. Христиане отстаивали уже одни только развалины, а между тем защищались все так же упорно. После нескольких постоянно отбитых приступов, янычары, стыдясь, что их останавливает горсть храбрых, бросились в брешь, взобрались на стену и водрузили на ней свое знамя, но еще раз железная и огненная стена уничтожила их натиск: дождь гранат, кипящего масла и других веществ сбросил их в ров. Гассан-Паша, раненный в лицо, собирает оставшихся в живых и еще раз ведет на приступ, но только для того, чтобы видеть окончательное поражение своих янычар.
