Niewola Zwolniony ze służby wojskowej po czterech latach, w drodze do kraju, został wzięty do niewoli przez berberyjskich korsarzy, którzy sprzedali go bejowi Algieru. Ponieważ miał ze sobą listy polecające od księcia de Sessa i Don Juana, cena okupu za niego była wyższa niż za przeciętnego chrześcijanina, a tym samym czas oczekiwania na wykupienie wydłużał się. Jednocześnie niewykluczone, że listy tak ważnych osób uratowały mu życie, gdy kilkakrotnie próbował ucieczki. Niewola trwała pięć lat; o jego obecności w Algierze wspominają co najmniej dwa źródła z tamtego okresu. Wydaje się, że dość krnąbrny jako niewolnik Cervantes był przez swych kolejnych właścicieli traktowany z pobłażaniem, a jego talent, zarówno przywódczy, jak i artystyczny, zyskał mu uznanie współtowarzyszy niedoli. Wreszcie w 1580 rodzina Cervantesa uzbierała 500 eskudów i Miguel został wykupiony, niemal w ostatniej chwili, bo jego ostatni właściciel przenosił się właśnie do Konstantynopola i zamierzał zabrać ze sobą wszystkich niesprzedanych niewolników.