Cervantes’in Cezayir’e gelişinden kısa bir süre sonra Hasan Paşa naip olarak Rabadan Paşa’nın yerine geçti. Bu Venedikli paşa, o kadar zalimdi ki Cezayirliler arasında bile öne çıkan bir isimdi. Cervantes kişiliğini Don Kişot’taki Esir’in ağzından anlatmıştır: “Açlık ve çıplaklık arada sırada, hatta neredeyse sürekli bizi rahatsız etse de hiçbir şey bizi efendimizin Hıristiyanlara gösterdiği eşi benzeri görülmemiş zalimlikleri görmek ya da duymak kadar rahatsız edemezdi. Her gün birini asıyor, başka birini mızraklıyor, üçüncü birinin ise kulaklarını kesiyordu ve bunları çok ufak bahanelerle, hatta bazen hiçbir bahane olmadan yapıyordu. Osmanlılar da efendimizin yalnızca canı istediği için böyle davrandığını ve doğası gereği vahşi bir adam olduğunu düşünüyorlardı.”
Kendi eğlencesi için işkence ettiği söylenen bu tiran, Cervantes’in esir olduğu beş yıl boyunca Cezayir’in efendisiydi. Cervantes esir alındıktan çok kısa bir süre sonra, hâlâ Déli Mami’nin kölesiyken yapacağı birçok kaçma girişiminin ilkini denedi. Bazı arkadaşlarıyla birlikte (o zamanlar İspanyol yerleşkesi olan) Oran’a karadan ulaşmaya çalıştılar; fakat grup, rehber olarak kiraladıkları Mağribi tarafından terk edilince Cezayir’e geri dönmek zorunda kaldılar. İki ya da üç girişimde daha bulunuldu, Cervantes bunları Cezayir’de Hayat’ta bizzat anlatmaktadır. İnanılmaz bir kurnazlık ve planlamada olağanüstü bir beceri sergilemesine rağmen her seferinde arkadaşlarından birinin ihaneti ya da korkaklığı nedeniyle planı suya düştü. Girişim başarısız olduğunda Cervantes ilk teslim olan ve suçu üstlenen kişi oluyordu.
Esirliğinin ikinci yılında Cervantes anavatanındaki bazı arkadaşlarıyla iletişim kurup onlara kendisinin ve kardeşinin acınası durumunu anlatmayı başardı. Babası Rodrigo yardım çağrısına para toplayıp Cezayir’e göndererek cevap verdi. Déli Mami bu meblağın Miguel kadar ileri gelen biri için yeterli olmayacağını söyleyerek Miguel’i serbest bırakmayı reddetse de kardeşi özgürlüğüne kavuşmayı başardı. Büyük kardeş serbest kalınca iki kardeş Miguel ve birkaç arkadaşını kurtarmak için bir plan yaptılar. Belli bir tarihte kıyıda belirecek silahlı bir İspanyol gemisinden yardım alacaklardı. Bu plan da diğerleri gibi inanılmaz derecede soğukkanlı, cesur ve fedakâr davranan Miguel’in elinde olmayan bir hata yüzünden suya düştü. Hasan adındaki bir Yunan haydudun bahçesinde, Cezayir’den üç kilometre uzakta, deniz kıyısında bir mağara vardı. Burada, çoğunluğu eski centilmenlerden oluşan kırk ya da elli kişilik bir grup saklanıyordu. Cervantes, Juan adında Navarreli bir köleyle onlara yemek gönderiyordu. Burada İspanya’dan gelip onları götürecek geminin gelmesini beklediler. Cervantes mağarada saklanan son kişi oldu. Belirlenen gün geldi. Mallorca’dan gönderilen bir fırkateyn esirlerle iletişim kurmayı başardı. Fakat Mağribi bir balıkçı korsanları uyardığı için gemi tekrar denize açılmak zorunda kaldı. Bu sırada Cervantes’in kurtarmak için sayısız fedakârlıkta bulunduğu insanlar arasında bir hain vardı. El Dorador (Yaldızcı) adında bir haydut korkmuş ve planı Naip’e bizzat bildirmişti. Naip mağaraya silahlı adamlarından oluşmuş kalabalık bir grup göndermişti. Planının başarısız olduğunu anlamakta gecikmeyen Cervantes, askerlerin önünde tüm planı kendisinin yaptığını ve diğerlerinin hiçbir suçunun olmadığını cesurca belirtti. Naip’in huzuruna getirildiğinde de ifadesini tekrarladı ve boynuna bir ip geçirilip, işkence görerek öldürülmekle tehdit edildiğinde bile kaçış planını tek başına yaptığını söyledi.
Naip’in bu esirle karşı karşıya geldiğinde sergilediği bazı davranışlar için hiçbir açıklama yok. Gazabından kimsenin kurtulamadığı, Cezayirlileri de rahatsız eden bir hayal gücü olduğu söylenen bu zalim adam, Cervantes’in cesareti karşısında ne yapacağını bilememiş gibi görünüyor. Cervantes’in zamanında Cezayir’de köle olanların ifadelerini eserinde derleyen Papaz Haedo’nun olağanüstü ifadesine göre Paşa sık sık “kendini bu sakat İspanyol’dan koruyabilirse adamlarını, gemilerini ve şehrini güvende tutabileceğini” söylerdi. Cervantes Don Kişot’ta göz yumulabilecek bir kibirle şöyle yazmıştı: “Ona karşı koyabilen tek kişinin özgürlüğünü kazanmak için unutulmayacak şeyler yapan, fakat efendisinin bir kere bile vurmadığı, kimseye dokundurtmadığı, hatta hakkında tek kötü söz bile söylemediği bir İspanyol askeri -Saavedra adında biri (Cervantes’in kendisi)– olduğu söyleniyordu.” Cervantes’in gördüğü bu tuhaf, benzersiz muafiyeti nasıl açıklayabiliriz? Onu olduğundan daha yüksek rütbeli sandıklarına şüphe yok; fakat yüksek bir fidye ihtimali, diğer değerli kölelerin maruz kaldıkları işkenceler ve aşağılanmalardan muaf tutulmasını açıklamaya yetmez. Bazıları, cesur ve korkusuz olduğunu gördükleri için onu Müslümanlığa geçirmek niyetinde oldukları tahmininde bulundu. Fakat Cervantes’in hayatında ya da Cezayir’deki davranışlarında gördüğümüz hiçbir şey bu teoriyi desteklemiyor. Başka bir teori ise Cervantes’in güçlü bir korsan kaptanıyla arkadaş olduğudur: Maltrapillo (Slovak) takma isimli Morato (Murat). Murcialı bu haydudun Hasan Paşa’nın en sevdiği haydutlardan biri olduğu iddia ediliyor. Bu iddia Cervantes’in köleliği sırasında Naip üzerinde gösterdiği etkiyi açıklamıyor; fakat belki de bunun sonucu olarak Hıristiyan köleler üzerinde gösterdiği etkiyi açıklıyor.
Korku saçan esirini kendine daha yakın tutmak isteyen Hasan Paşa, onu efendisi Déli Mami’den 500 altın karşılığında satın aldı. Artık Naip’in esiri olan Cervantes geleneğe göre tüm angarya işlerden muaftı, fakat hâlâ zincire vurulması gerekiyordu. Köle olmasının üzerinden iki yıl geçmişti. İspanya kralının kâtibi Mateo Vasquez’e şiirsel mektubunu yazdı. Bu mektup yirmi beş yıl kadar önce Altamira ailesinin arşivlerinde keşfedildi ve Cervantes’in biyografisiyle bağlantılı en önemli belgelerden biri haline geldi. Seksen bir bentten oluşan ve Parnassus’a Yolculuk’un hece ölçüsünü kullanan bu şiir, otobiyografik bir tasvirle başlar. Şair, denizde ve karada yaptığı işleri anlatır ve Cezayir’deki Hıristiyan kölelerin ayaklanmasını, İspanyol donanmasının da onlara yardım etmesini teklif ederek bitirir. Kralın olağanüstü babası V. Charles’ın başladığı işi bitirmesi için yalvarır. İspanyol donanmasının gelip hücre kapılarını açmasını dört gözle bekleyen zavallı Hıristiyanlara acıması için ona yakarır. Şair anavatanlarının kutsal kıyısını neredeyse görebilecek kadar yakın olan fakat zincirler içinde kıvranan zavallıların durumunun soylu kalpleri acımayla dolduracağına emindir.
Düşmanın ülkesi zayıftı, şehirleri iyi savunulmuyordu, muhafızları soy ve ırk olarak farklıydı, yalnızca ortak bir inanç ve kazanç tutkusuyla bir arada duruyorlardı. Bu macera umutsuz sayılmazdı ve II. Philip şövalyelikten ya da ulusal görev duygusundan bir nebze bile etkilenmiş olsaydı