Πίσω από τον Ι.Ν. Αγίου Ανδρέα Ερεσού βρίσκεται σε ερειπιώδη κατάσταση η παλαιοχριστιανική βασιλική, πίσω από την οποία ετάφη το 740 μ.Χ. ο άγιος Ανδρέας αρχιεπίσκοπος Κρήτης, ο οποίος πέθανε εν πλω μπροστά στην Ερεσό διερχόμενος από την Κωνσταντινούπολη. Ο ναός ήταν αφιερωμένος πιθανώς στην αγία μάρτυρα Αναστασία, όμως έμεινε γνωστή ως βασιλική του αγίου Ανδρέα. Πρόκειται για μια από τις μεγαλύτερες σε έκταση παλαιοχριστιανικές βασιλικές της Λέσβου με ορθογώνια κάτοψη.
Αποκαλύφθηκε μετά από ανασκαφές των μοναχών της Ι.Μ. Πιθαρίου το 1884-1885. Έχει τρίκλιτη διάταξη και αποτελείται από νάρθηκα, κυρίως ναό και ιερό βήμα. Η αψίδα του ιερού είναι εσωτερικά εγγεγραμμένη κυκλική, ενώ εξωτερικά πολύπλευρη, τύπος ο οποίος προήλθε από το Συρία. Επιγραφή σε διάχωρο του δυτικού τμήματος δαπέδου που αναφέρει τον επίσκοπο Ιωάννη, ο οποίος εκπροσώπησε τους Λέσβιους στην Γ’ Οικουμενική Σύνοδο, όπως επίσης και τα ψηφιδωτά που κοσμούν το δάπεδο του ναού, μαρτυρούν στοιχεία για τη χρονολόγηση του ναού κατά τις αρχές του 5ου αιώνα ίσως και νωρίτερα.
Σε ικανό ύψος σώζονται, επίσης, τοίχοι μικρού παλιού παρεκκλησίου αφιερωμένου στον άγιο Ιωάννη τον Πρόδρομο, όπως επίσης και βοηθητικοί χώροι του ναού. Στο πίσω μέρος του ναού υπάρχει έως σήμερα το μαυσωλείο με την κενοτάφια σαρκοφάγο του αγ. Ανδρέα Κρήτης.
