Вернувшись к должности, Хасан разгромил марокканские силы, которые снова осадили Тлемсен, и выступил на Фес, у которого турки в 1557 году были разбиты и отступили. Одновременно им угрожали испанцы из Орана. Последние в этот момент атаковали Мостаганем. Предприятие в 1558 году закончилось для них катастрофой и стало последней попыткой испанцев расширить сферу влияния за пределы Орана. В 1561 году планы Хасана продолжать операции на западе были прерваны заговором турецких солдат, которым не нравилось использование им местных войск, берберов и арабов. Его обвинили в попытке стать независимым. Хасан был отправлен в Константинополь в цепях, но сумел оправдаться и в следующем, 1562 году вернулся в Алжир. Он как раз готовился напасть на Оран, когда в 1565 году его призвали принять участие в осаде Мальты, после чего в 1567 году он стал командующим флотом Османской империи — капудан-пашой. Годом позже его сменил на посту наместника Алжира Али-паша (1568–1587), бывший житель Калабрии, захваченный в плен еще юношей и принявший ислам, когда был рабом на галерах. Сразу после его вступления в должность имело место восстание морисков в Гранаде. Представляется, что Али-паша собирался им помочь, но султан приказал ему напасть на Тунис. Испанцы все еще находились в Голетте, откуда руководили марионеточным правителем. В 1569 году, захватив город (но не Голетту), он водворил турецкого правителя. Двумя годами позже, в 1571 году, турецкие военно-морские силы потерпели сокрушительное поражение от испанцев при Лепанто. Али-паша, отличившийся в боях на турецкой стороне, был назначен капудан-пашой. Воодушевленные победой при Лепанто испанцы, которыми командовал Дон Хуан Австрийский, в 1573 году внезапной атакой захватили Тунис. Успех был мимолетным, поскольку уже в следующем, 1574 году Али-паша, организовав атаку из Алжира и Триполи (который был турецким с 1551 года), захватил не только Тунис, но также крепость в Голетте, где испанцы находились в 1534 году. Это стало концом затянувшейся испано-турецкой борьбы за господство в центральной и восточной части Магриба. У испанцев остался там лишь один плацдарм — город Оран. Пока Али-паша занимал должность капудан-паши, Алжиром управляли «заместители»: сначала Араб Ахмад, затем Рамадан (1574–1577), сын сардинского пастуха, захваченный еще в детстве. В 1576 году он завоевал Фес для Саадита Абд аль-Малика. После него был Хасан Венецианец, имевший венецианское происхождение, как показывает имя. Последний был пашой во время пленения Сервантеса, который описывал его гордость, жестокость и энергию. После восстания против него пашой стал Джафар, евнух венгерского происхождения, также захваченный в детстве. При нем Али-паша готовился лично возглавить экспедицию против султана Марокко из Саадитов, Ахмада аль-Мансура. Этому помешал отзыв в Константинополь по срочным делам. После смутного времени, ненадолго приведшего к власти Мами Арнута, Хасан Венецианец вернулся и правил с 1582 до 1588 года. После смерти Али-паши в 1587 году на должность капудан-паши был назначен Хасан Венецианец, который перестал быть наместником Алжира. Учитывая относительно стабильную ситуацию в османских регентствах — Алжире, Тунисе и Триполи, — впоследствии ими управляли бейлербеи. Каждый из них имел титул паши и назначался на три года с возможностью продления срока. Все три государства теперь имели организацию, которая определяла их характер на протяжении следующих двух веков.