Από τα σημαντικότερα μνημεία του αρχαιολογικού χώρου του Βουθρωτού είναι και η μεγάλη παλαιοχριστιανική βασιλική.
Το σχήμα της είναι μια τρίκλιτη Βασιλική με εγκάρσιο κλίτος η οποία θυμίζει το κάτοπτρο του Αγίου Δημητρίου στη Θεσσαλονίκη.
Σύμφωνα με την αρχαιολογική μαρτυρία ο ναός πρέπει να κτίστηκε περίπου τον 6ο αιώνα ενώ σημαντικές επεμβάσεις έγιναν στη διάρκεια των επόμενων αιώνων.
Ωστόσο τα ελάχιστα ψηφιδωτά που σώζονται στο δάπεδο του ναού μπορεί να μεταφέρουν τη χρονολόγηση του ακόμη και τον 4ο αιώνα.
Δεν καμία ιστορική πηγή που να τεκμηριώνει το γεγονός της αφιέρωσης του ναού σε κάποιον Άγιο. Σε κάποια δημοσιεύματα αναφέρεται ως ναός των Αποστόλων Πέτρου και Παύλου, χωρίς όμως να το γνωρίζουμε με ακρίβεια. Ίσως ήταν αφιερωμένος προς τιμήν του Αποστόλου Παύλου που μετέφερε τον χριστιανισμό στην ευρύτερη περιοχή.
Πιθανότατα ο απόστολος των εθνών, στο δρόμο του από Μακεδονία προς Ρώμη (64-66 μ.χ.) διήλθε και από τα τότε μεγάλα αστικά κέντρα της Ηπείρου όπως τη Νικόπολη, το Βουθρωτό και την Επίδαμνο.
Μάλιστα ως πρώτος Επίσκοπος της Επιδάμνου (σημερινό Δυρράχιο) αναφέρεται ο μαθητής του Παύλου, Άγιος Άστειος.
