Laut der Legende war der bekannte spanische Schriftsteller Miguel de Cervantes Ende des 16. Jahrhunderts Sklave in Ulcinj. Einige Forscher erkannten in seiner Romanfigur Dulcinea von Toboso, der weiblichen Hauptrolle seines Buches „Don Quixote“, eine Frau aus Ulcinj. Tatsächlich entstand „Don Quixote“ nach Cervantes‘ Sklaverei in der Altstadt, die in den römischen Staaten Dulcinjo genannt wurde und noch heute existiert. Bedeutet das, dass Dulcinea nur ein anderer Name für eine Frau aus Ulcinj war? Die Volksüberlieferung erwähnt einen Servet, dessen Schicksal und dessen Name mit dem von Cervantes übereinstimmen.
Ein Blick in viele Texte führt uns zur Entdeckung, dass der 24-jährige Cervantes „eines Tages im Jahr 1575 als drei Ulcinj-Leuts – schnelle Piratenboote unter dem Kommando des berüchtigten Kapitäns Arnaut Mami – ein spanisches Fregattenschiff im Mittelmeer angriffen. In dem blutigen Kampf überwältigten die Piraten die kämpferischen Spanier und nahmen das Schiff mit den Gefangenen in ihren Hafen. Unter den Gefangenen war ein Mann mit einer besonderen Empfehlung des spanischen Königs. Das bedeutete, dass er ein wertvoller Sklave war, der ihnen viel Gold bringen würde“. Die Einheimischen nannten ihn Servet, was eigentlich die Grundlage für den später bekannten Spanier war. Sein Verhalten wurde mit besonderer Sorgfalt überwacht.
Dieser Sklave würde, wie die Einwohner der Altstadt bemerkten, bis spät in die Nacht in seiner Zelle wach bleiben, ständig nachdenken und schreiben. Tagsüber würde er immer singen, so dass Mädchen oft zu ihren Fenstern herauskamen, um ihm zuzuhören. Für eines der Mädchen, wie die Tradition besagt, war dies nicht genug, so dass sie ihm jedes Mal folgte, wenn der Sklave Servet entlang der erlaubten Wege spazieren ging. So entstand die Liebe zwischen dem Mädchen aus der Region und dem unbekannten Sklaven.
Ein paar Jahre später kam ein Fremder und brachte viel Geld mit und befreite den Sklaven, der dann das schöne Mädchen aus der Altstadt mitnahm. Nach einer anderen Überlieferung brachte der Eigentümer Miguel nach Algerien, also nach Berberia, mit der die Einwohner von Ulcinj enge Beziehungen hatten. Dort kaufte ihn ein gewisser Hasan-aga, einer der grausamsten lokalen Anführer. Von dort aus gelang es Cervantes zu entkommen, dank der spanischen Mönche, die das Lösegeld für ihre Landsleute im Mittelmeer zahlten.
Sie mussten 500 goldene Taler bezahlen, damit er nach fünf Jahren harter Sklaverei endlich spanischen Boden betreten konnte. Darauf folgte der Roman „Don Quixote“ mit der Geschichte von Dulcinea, der Frau aus Ulcinj. Es ist unbestritten, dass Cervantes vor seiner Befreiung im September 1580 und bevor er nach Spanien aufbrach, sich gegen Vorwürfe verteidigen musste, er habe mit den berberischen Piraten zusammengearbeitet. Möglicherweise kam er mit ihnen nach Ulcinj oder hörte Geschichten über den „Hafen Dolcinjo“, die entweder von ihnen oder anderen Gefangenen von jenseits des Meeres erzählt wurden. Diese Geschichte oder Legende hat den Namen Ulcinj perpetuiert.