Η παλαιοχριστιανική βασιλική Χαλινάδου βρίσκεται στην ομώνυμη θέση της αγροτικής περιφέρειας της κοινότητας Αγίας Παρασκευής Λέσβου. Η βασιλική αποτελούσε πιθανότατα το καθολικό μικρού μοναστηριού όπως προκύπτει από τα λείψανα τοίχων των κελιών που διασώζονται κατά τη νότια πλευρά της. Αρχιτεκτονικά μέλη από την παλαιοχριστιανική βασιλική εντοπίζονται στα ερείπια δύο κοντινών μεταβυζαντινών ναών (στο ερειπωμένο εκκλησάκι- υπαίθριο εικονοστάσι της Παναγίας, σε απόσταση 70 μ. από αυτή και στον Άγιο Δημήτριο πάνω σε παρακείμενο μικρό λόφο).

Για την ίδρυση της παλαιοχριστιανικής βασιλικής δεν έχουμε στη διάθεση μας ιστορικές μαρτυρίες, ωστόσο με βάση τα στιλιστικά χαρακτηριστικά της μορφής και της διακόσμησης των κιονόκρανων της μπορούσε να τοποθετήσουμε την ανέγερση της στο δεύτερο μισό του 6ου αι. μ.Χ. Σε αυτή τη χρονολόγηση συνηγορεί και ο εντοπισμός ενός χάλκινου νομίσματος της εποχής του Μαυρικίου Τιβερίου (587-8 μ.Χ.).

Η βασιλική του Χαλινάδου ανήκει στον τύπο της τρίκλιτης ξυλόστεγης βασιλικής με νάρθηκα. Ο κυρίως ναός έχει στην κάτοψη σχήμα περίπου τετράγωνο. Στα ανατολικά δεσπόζει η προεξέχουσα ημικυκλική αψίδα του ιερού. Στα δυτικά είναι προσκολλημένος ο νάρθηκας, πλάτους 5.96 μ., ο οποίος εξέχει του σώματος του ναού κατά τη νότια πλευρά. Στη βόρεια του πλευρά δημιουργούνται δύο ανοίγματα ενώ στη νότια ακόμα ένα. Ο ναός ήταν ξυλόστεγος όμως η αψίδα του ιερού καλυπτόταν κατ' εξαίρεση με κτιστό θόλο (τεταρτοσφαιρικό), όπως συνάγεται από το μεγάλο πάχος των τοίχων της (1.15 μ.).

Δύο κιονοστοιχίες αποτελούμενες από δύο παραστάδες και πέντε κίονες η κάθε μία διαιρούν τον κυρίως ναό σε τρία κλίτη από τα οποία το μεσαίο είναι ευρύτερο από τα πλάγια. Οι κιονοστοιχίες βαίνουν πάνω σε ψηλό στυλοβάτη, ύψους 0.50 μ., όπως συνηθίζεται και σε άλλες παλαιοχριστιανικές βασιλικές της Λέσβου (Υψηλομέτωπο, Αφεντέλλη). Οι κίονες αποτελούνται από βάση, κορμό και κιονόκρανα και είναι μονολιθικοί και αρράβδωτοι, κατασκευασμένοι από εγχώριο ερυθρωπό ασβεστόλιθο. Οι βάσεις των κιόνων διαμορφώνονται με μία τετράγωνη πλίνθο και ένα λοξότμητο μέλος που αντικαθιστά την αρχαία σπείρα. Τα κιονόκρανα παρουσιάζουν τη συνηθισμένη στα παλαιοχριστιανικά μνημεία μορφή, ιωνικού τύπου με επίθημα, και χαρακτηρίζονται από αμέλεια ως προς την κατασκευή. Οι κίονες έφεραν ημικυκλικά τόξα διαμέτρου 2 μ. κατασκευασμένα από σφηνοειδείς πωρόλιθους. Λίθινη διακοσμητική ταινία περιέτρεχε το ναό και το τεταρτοσφαίριο της αψίδας στο ύψος της γέννησης του.

Η αψίδα διαμόρφωνε στο εσωτερικό της κτιστό σύνθρονο και αμέσως μπροστά από το ιερό ήταν τοποθετημένη η Αγία Τράπεζα. Από την Αγία Τράπεζα βρέθηκαν κατά την ανασκαφή μόνο τμήματα του κιβωρίου που τη στέγαζε. Εντοπίστηκαν επίσης τμήματα του φράγματος πρεσβυτερίου (πεσσίσκοι, θωράκια κ.α.) τα οποία δεν είναι επαρκή για να αποκαταστήσουμε με ασφάλεια τη μορφή του.

Γλυπτά που βρέθηκαν κατά την ανασκαφή του μεσαίου κλίτους προέρχονται από τον άμβωνα του ναού. Η μορφή του ήταν η συνηθισμένη στα παλαιοχριστιανικά χρόνια ενός κυκλοτερούς σώματος με δύο κλίμακες ανόδου. Το δάπεδο του ναού ήταν στρωμένο με μεγάλες πλάκες από τις οποίες διατηρούνται σε καλή κατάσταση αυτές του νοτίου κλίτους.

Το ναό ανέσκαψε το 1937 και αναστήλωσε μερικώς ο καθηγητής Α. Ορλάνδος με δαπάνες του Υπουργείου Θρησκευμάτων και Εθνικής Παιδείας και της κοινότητας Αγ. Παρασκευής.