Πολύ διαδεδομένος, ιδίως κατά τα Μεσαιωνικά Χρόνια, θρησκευτικός θρύλος, που απαντάτο και σε σχέση προς την Κύπρο και ιδιαίτερα την Πάφο. Σύμφωνα προς τον θρύλο αυτόν, οι «Επτά Κοιμώμενοι» ήσαν Χριστιανοί νέοι που έζησαν κατά τον 3ο μ.Χ. αιώνα. Κατά την περίοδο των διωγμών των Χριστιανών επί Δεκίου (201-251 μ.Χ.), κατέφυγαν κυνηγημένοι σε ένα σπήλαιο ˙ οι διώκτες τους έκλεισαν τότε και σφράγισαν το στόμιο του σπηλαίου εκείνου, προκειμένου να πεθάνουν μέσα εκεί από πείνα και δίψα οι επτά Χριστιανοί νέοι. Εκείνοι όμως, αντί να πεθάνουν, βυθίστηκαν αμέσως σε έναν βαθύ ύπνο, λόγω θαύματος.
Μετά δε από 200 (κατά μία εκδοχή) ή 300 (κατ' άλλη εκδοχή) χρόνια, κατά δε μία τρίτη εκδοχή επί αυτοκράτορος Θεοδοσίου Β' (408-450), και όταν πλέον ο Χριστιανισμός είχε οριστικά επιβληθεί, ένας βοσκός έτυχε να βρει και να ανοίξει το σπήλαιο. Και τότε οι επτά κοιμώμενοι νέοι ξύπνησαν!
Ο θρύλος αυτός ήταν πολύ παλαιός, η δε αρχαιότερη γι' αυτόν αναφορά απαντάται σε ένα συριακό κείμενο του 6ου αιώνα. Παρά το ότι ο θρύλος ήταν ευρύτατα διαδεδομένος σε πολλά μέρη, και ομιλούσε μάλιστα για επτά ευγενείς νέους από την Έφεσο, κατά τα Μεσαιωνικά Χρόνια εθεωρείτο ότι το γεγονός είχε συμβεί στην Κύπρο, και μάλιστα στην Πάφο. Σχετικές αναφορές κάνουν διάφοροι μεσαιωνικοί επισκέπτες της Κύπρου, που αναφέρουν μάλιστα ότι στην Πάφο ένα σπήλαιο υποδεικνυόταν στους ξένους ως εκείνο στο οποίο είχαν εγκλωβισθεί οι επτά κοιμώμενοι. Ένας όμως επισκέπτης, ο Γάλλος ιερέας Πιέρ Μπαρμπάτρ, που είχε επισκεφθεί την Κύπρο το 1480, κάνει λόγο για έναν «βράχο στον οποίο κοιμήθηκαν για 300 χρόνια οι Επτά», στη Λευκωσία, στη (δυτική) άκρη της πόλης. Άρα, για κάποιο διάστημα, ο θρύλος ετοποθετείτο και σ' αυτή τη Λευκωσία. Όπου, ο «βράχος της κοιμήσεως των Επτά» θα πρέπει να ήταν, πιθανότατα, ένας αρχαίος λαξευτός τάφος, μάλλον με επτά ταφικές θήκες στο εσωτερικό του, αυτός δε ο αριθμός των ταφικών θηκών (επτά) θα πρέπει να συνέτεινε ώστε ο αρχαίος τάφος να συνδεθεί με τον θρύλο των «Επτά Κοιμωμένων». Το ίδιο ακριβώς είναι φανερό από τις αναφορές ότι είχε συμβεί και στην Πάφο. Όπου, δηλαδή, ένας αρχαίος τάφος με επτά ταφικές θήκες, θεωρήθηκε ότι ήταν ο χώρος όπου κοιμήθηκαν οι επτά νέοι του θρύλου.
Ένας επισκέπτης του 1480, κάποιος Γάλλος κληρικός του οποίου το όνομα δεν διασώθηκε, ομιλεί για το σπήλαιο των «Επτά Κοιμωμένων», που όμως το είχε δει «στους πρόποδες ενός βουνού, μισό μίλι από τη Λευκωσία». Ως «βουνό» θα εννοούσε μάλλον τον λόφο της Αγίας Παρασκευής (τον χώρο των αρχαίων Λεδρών), όπου υπήρχαν πολλοί αρχαίοι τάφοι, εκ των οποίων και πάλιν ένας θεωρήθηκε ως εκείνος των «Επτά Κοιμωμένων». Όπου, κατά τον Γάλλο κληρικό, «εκρύβησαν για 300 χρόνια και βγήκαν ύστερα όλοι ζωντανοί».
Ο Γάλλος συγγραφέας, ιστοριοδίφης και γεωγράφος Αντρέ Θεβέτ (δεν είναι γνωστό πότε ακριβώς επεσκέφθη την Κύπρο, αλλά πάντως κατά το δεύτερο μισό του 16ου αιώνα), γράφει ότι είχε ο ίδιος ξεναγηθεί επανειλημμένα στο σπήλαιο που ήταν ευρύτατα γνωστό ως εκείνο των «Επτά κοιμωμένων», στην Πάφο. Υπήρχε τότε εκεί ένα παρεκκλήσι, γράφει, γνωστό ως «Οι Επτά Κοιμώμενοι», στο βάθος δε του σπηλαίου ευρισκόταν και ο τάφος του αγίου Σαπρικίου, επισκόπου της Πάφου κατά το πρώτο μισό του 5ου αιώνα (είχε πάρει μέρος στην σύνοδο του 431 στην Έφεσο). Ο Αντρέ Θεβέτ δεν πίστεψε στον θρύλο των «Επτά Κοιμωμένων» και γράφει ότι «ο λαός ευρισκόταν σε τέτοια πλάνη, ώστε νόμιζε ότι οι επτά νέοι ήσαν ακόμη ζωντανοί». Προσθέτει δε ότι «οι ιερείς συντηρούν ακόμη αυτό το λάθος». Ο Θεβέτ είναι και αρκετά διαφωτιστικός ως προς την τοποθεσία του σπηλαίου του θρύλου, λέγοντας ότι αυτό ευρισκόταν «μεταξύ της πόλης της Πάφου — τώρα ερειπωμένης σε μεγάλο βαθμό — και του πύργου κοντά στην θάλασσα...»
Συνεπώς το σπήλαιο στην Πάφο, που υποδεικνυόταν ως εκείνο των «Επτά Κοιμωμένων», θα πρέπει να ήταν είτε μία από τις σωζόμενες ως σήμερα «κατακόμβες» της περιοχής (Αγίας Σολομωνής ή Αγίου Λαμπριανού), είτε κάποια από τις παραπλήσιες «στοές» με υπόγειους θαλάμους που αποτελούσαν τμήματα των οχυρώσεων της αρχαίας Πάφου.
Ο Φινς Μόρυσον πάλι, ένας Άγγλος ταξιδιώτης που πέρασε από την Κύπρο το 1596, τα λέγει διαφορετικά: «ένα μίλι μακριά από αυτό τον τόπο [=την Πάφο] υπάρχει ένα σπήλαιο όπου λέγεται ότι οι Επτά Κοιμώμενοι είχαν κοιμηθεί, κι εγώ δεν ξέρω πόσες εκατοντάδες χρόνια...»
Ομιλώντας για σπήλαιο σε απόσταση ενός μιλίου από την Πάφο, προφανώς ο επισκέπτης αυτός θα εννοούσε έναν από τους γνωστούς ως «Τάφους των Βασιλέων», και συνεπώς την εποχή της δικής του επόσκεψης, ο θρύλος είχε «μεταφερθεί» έξω από την πόλη της Πάφου.
Ο Τσέχος ευγενής Κρίστοφ Χάραντ, που πέρασε από την Κύπρο το 1598, περίπου σύγχρονος του Μόρυσον, ομιλεί επίσης για «υπόγεια κτίσματα και επτά σπηλιές» όπου αναπαύονταν οι «Επτά Κοιμώμενοι», κοντά σε ένα «ερειπωμένο μοναστήρι», στην περιοχή της Πάφου. Προφανώς και πάλι εννοούντο εδώ οι «Τάφοι των Βασιλέων», με την πρόσθετη πληροφορία ότι στην περιοχή υπήρχε τότε (1598) και ένα ερειπωμένο μοναστήρι. Στον ίδιο χώρο, τους «Τάφους των Βασιλέων», κάποιοι θάλαμοι υποδεικνύοντο ως το μέρος στο οποίο είχαν φυλακιστεί οι απόστολοι Βαρνάβας και Παύλος, κατά την πρώτη τους αποστολική περιοδεία, το 45 μ.Χ.
Ευρύτατα διαδεδομένος ήταν και ο θρύλος ότι σε σπήλαιο της Πάφου (=σε αρχαίο τάφο) είχαν δήθεν φυλακιστεί για κάποιο διάστημα οι δύο απόστολοι, πράγμα εντελώς αστήρικτο και ανυπόστατο.
Ωστόσο είναι πιθανόν ο Κρίστοφ Χάραντ να εννοούσε όχι τους «Τάφους των Βασιλέων» αλλά τις «κατακόμβες» Αγίας Σολομωνής και Αγίου Λαμπριανού, οπότε το κατεστραμμένο κοντινό μοναστήρι θα πρέπει να ήταν εκείνο του τάγματος των Φραγκισκανών. Εάν δε και ο Μόρυσον εννοούσε ότι ο χώρος ευρισκόταν ένα μίλι από την πόλη πάνω στον λόφο (το Κτήμα), τότε πιθανώς και αυτός εννοούσε τον ίδιο χώρο, και όχι τους «Τάφους των Βασιλέων». Ωστόσο και ο Γάλλος βαρώνος Ερρίκος ντε Μποβώ, που είχε επισκεφθεί την Κύπρο μάλλον περί το 1605, ομιλεί για «σπηλιές σε απόσταση ενός μιλίου» από την Πάφο, «στις οποίες λέγεται ότι οι Επτά Κοιμώμενοι είχαν κοιμηθεί περισσότερα από 300 χρόνια...»
Σαφώς, πάντως, στην περιοχή της αρχαίας Πάφου (σημερινή Κάτω Πάφος) όπου και οι «κατακόμβες» Αγίας Σολομωνής και Αγίου Λαμπριανού, τοποθετεί τον χώρο ο Άγγλος περιηγητής και σημαντικός επισκέπτης της Κύπρου (κατά το 1738) Ρίτσαρντ Πόκοκ. Εκεί, γράφει, «υπάρχει μία υπόγεια εκκλησία, λαξευμένη στον βράχο, αφιερωμένη στους Επτά Κοιμωμένους...»
Προκύπτει από όλες τις πιο πάνω αναφορές ότι οι «Επτά Κοιμώμενοι» εθεωρούντο άγιοι και ετιμώντο από την Εκκλησία, έως και τον 18ο αιώνα ακόμη. Ωστόσο ο θρύλος δεν διέσωσε οποιαδήποτε συγκεκριμένα ονόματα γι' αυτούς τους επτά. Είναι δε αξιοσημείωτο ότι ο θρύλος περί αυτών ετοποθετείτο και στην Λευκωσία και στην Πάφο, για να «καθιερωθεί» όμως από τον 16ο αιώνα αποκλειστικά στην Πάφο. Αργότερα (δηλαδή μετά τα μέσα του 18ου αιώνα), ο θρύλος δεν απαντάται πλέον. Προφανώς εγκαταλείφθηκε, ίσως ύστερα από «παραδοχή» της Εκκλησίας ότι δεν ευσταθούσε — ή ότι δεν σχετιζόταν με την Κύπρο. Ίσως μάλιστα κατόπιν αυτού, οι «κατακόμβες» της Πάφου να «απεδόθησαν» σε άλλους αγίους.
Αξιοσημείωτο είναι επίσης το γεγονός ότι ο Κύπριος χρονικογράφος Λεόντιος Μαχαιράς (15ος αιώνας), που ασχολήθηκε στο έργο του και με τους αγίους της Κύπρου, απαριθμώντας μάλιστα και τους χώρους λατρείας των, δεν αναφέρει τίποτα για τους «Επτά Κοιμωμένους». Θα ήταν παράξενο να μην γνώριζε περί αυτών, όταν μάλιστα οι ξένοι επισκέπτες τους μάθαιναν από αφηγήσεις και ξεναγήσεις των ντόπιων. Φαίνεται ότι η επίσημη Εκκλησία δεν αναγνώριζε, ίσως, τότε τον θρύλο για τους «Επτά», και για τον λόγο αυτό τους είχε αγνοήσει και παραλείψει και ο Λεόντιος Μαχαιράς.