История однорукого пленника стала известна в Алжире и привлекла к нему внимание самого правителя Гассан-паши по прозвищу Венециано. Вскоре Сервантес попал к нему — он с ужасом вспоминал об этом изверге в романе «Дон Кихот»:
Но Сервантес продолжал борьбу за свободу. Он отыскал человека, который взялся переправить коменданту Орана письмо с просьбой организовать побег. И вновь последовал провал — гонец был схвачен на границе и казнен, а Сервантеса приговорили к 2 тыс. палочных ударов, но, к счастью, в последний момент экзекуцию отменили. В сентябре 1579 года Сервантес предпринял четвертую попытку вырваться из неволи. На этот раз его союзниками стали испанские купцы, проживавшие в Алжире. Они приобрели небольшую фелюгу и должны были вывезти шестьдесят рабов в Испанию. Измена вновь встала на пути освобождения. Участник заговора, доминиканский монах Хуан Бланке де Пас, выдал весь план алжирским властям — всего одно золотое эскудо и кувшин масла получил предатель от Гассана Венеииано, а жизнь нескольких десятков человек была перечеркнута. Когда стало известно, что заговор раскрыт, Сервантес укрылся в городе у верных друзей, готовых рискнуть за него жизнью. Гассан-паша начал поиски бежавшего. Глашатай объявлял на площадях и улицах Алжира о том, что за раскрытие местонахождения Сервантеса будет выплачено большое вознаграждение, тому же, кто укрывает его, грозили смертной казнью. Опасаясь за будущее своих друзей, Сервантес вышел из укрытия и явился к Гассан-паше. Его долго допрашивали, пытали и требовали назвать сообщников, но Сервантес держался твердо и никого не выдал. Дело для него, по-видимому, закончилось бы смертью, если бы не заступничество одного влиятельного алжирского раиса, испанца по происхождению. Сервантеса опять посадили в кандалы и бросили в застенок.
Пока в Алжире происходили эти драматические события, семья Сервантеса искала средства для выкупа Мигеля. Наконец в 1580 году было собрано 3 тысячи реалов. Их вручили главе специальной миссии, отправленной в Алжир для освобождения невольников. На этот раз фортуна улыбнулась Сервантесу. Гассан-паша получил от турецкого султана распоряжение сложить полномочия правителя Алжира и явиться в Константинополь. Он назначил за Сервантеса выкуп в 500 эскудо, а освобождение второго своего пленника, дона Херонимо Палафокса, выходца из знатного рода, расценил в 1000 эскудо. Сколько ни бился испанский агент, он не смог снизить выкуп — решение Гассан-паши было твердым. Настало 19 октября, день отъезда Гассан-паши в Константинополь — в столице османов пленники терялись навсегда и уже не возвращались. Испанский агент провел с ним последнюю беседу и отправился выкупать Сервантеса — дона Херонимо же увезли в Константинополь.