Η παλαιοχριστιανική βασιλική Χαλινάδου βρίσκεται στην ομώνυμη θέση της αγροτικής περιφέρειας της κοινότητας Αγίας Παρασκευής. Η βασιλική αποτελούσε πιθανότατα το καθολικό μικρού μοναστηριού, όπως προκύπτει από τα λείψανα τοίχων των κελιών που διασώζονται κατά τη νότια πλευρά της. Αρχιτεκτονικά μέλη από την παλαιοχριστιανική βασιλική εντοπίζονται στα ερείπια δύο κοντινών μεταβυζαντινών ναών.
Για την ίδρυση της βασιλικής δεν έχουμε ιστορικές μαρτυρίες, ωστόσο με βάση τα στιλιστικά χαρακτηριστικά της μορφής και της διακόσμησης των κιονόκρανών της μπορούμε να τοποθετήσουμε την ανέγερσή της στο δεύτερο μισό του 6ου αι. μ.Χ.. Σ’ αυτή τη χρονολόγηση συνηγορεί και ο εντοπισμός χάλκινου νομίσματος της εποχής του Μαυρικίου Τιβερίου (567-8 μ.Χ.).Η βασιλική του Χαλινάδου ανήκει στον τύπο της τρίκλιτης ξυλόστεγης βασιλικής με νάρθηκα. Ο κυρίως ναός έχει στην κάτοψη σχήμα περίπου τετράγωνο. Στα ανατολικά δεσπόζει η προεξάρχουσα ημικυκλική αψίδα του ιερού. Στα δυτικά είναι προσκολλημένος ο νάρθηκας, πλάτους 5,96 μ., ο οποίος εξέχει του σώματος του ναού κατά τη νότια πλευρά. Στη βόρεια πλευρά δημιουργούνται ανοίγματα ενώ στη νότια ακόμα ένα. Ο ναός ήταν ξυλόστεγος, όμως η αψίδα του ιερού καλυπτόταν κατ’ εξαίρεση με κτιστό θόλο (τεταρτοσφαιρικό), όπως συνάγεται από το μεγάλο πάχος των τοίχων της.
Δύο κιονοστοιχίες αποτελούμενες από δύο παραστάδες και πέντε κίονες η κάθε μια διαιρούν τον κυρίως ναό σε τρία κλίτη από τα οποία το μεσαίο είναι ευρύτερο απ’ τα πλάγια. Οι κιονοστοιχίες βαίνουν πάνω σε ψηλό στυλοβάτη, ύψους 0,50 μ., όπως συνηθίζεται και σε άλλες παλαιοχριστιανικές βασιλικές της Λέσβου (Υψηλομέτωπο, Αφεντέλλη). Οι κίονες αποτελούνται από βάση, κορμό και κιονόκρανα και είναι μονολιθικοί και αρράβδωτοι, κατασκευασμένοι από εγχώριο ερυθρωπό ασβεστόλιθο. Οι βάσεις των κιόνων διαμορφώνονται με μια τετράγωνη πλίνθο και ένα λοξότμητο μέλος που αντικαθιστά την αρχαία σπείρα. Τα κιονόκρανα παρουσιάζουν τη συνηθισμένη στα παλαιοχριστιανικά μνημεία μορφή, ιωνικού τύπου με επίθημα, και χαρακτηρίζονται από αμέλεια ως προς την κατασκευή. Οι κίονες έφεραν ημικυκλικά τόξα διαμέτρου 2 μ. κατασκευασμένα από σφηνοειδείς πωρόλιθους. Λίθινη διακοσμητική ταινία περιέτρεχε το ναό και το τεταρτοσφαίριο της αψίδας στο ύψος της γέννησής του.
Η αψίδα διαμόρφωνε στο εσωτερικό της κτιστό σύνθρονο και αμέσως μπροστά από το ιερό ήταν τοποθετημένη η αγία Τράπεζα. Από την αγία Τράπεζα βρέθηκαν κατά την ανασκαφή μόνο τμήματα του κιβωρίου που την στέγαζε. Εντοπίστηκαν επίσης τμήματα του φράγματος πρεσβυτερίου (πεσσίσκοι, θωράκια κ.α.), τα οποία δεν είναι επαρκή για την ασφαλή αποκατάσταση της μορφής του.
Γλυπτά που βρέθηκαν κατά την ανασκαφή του μεσαίου κλίτους προέρχονται από τον άμβωνα του ναού. Η μορφή του ήταν η συνηθισμένη στα παλαιοχριστιανικά χρόνια ενός κυκλοτερούς σώματος με δύο κλίμακες ανόδου. Το δάπεδο του ναού ήταν στρωμένο με μεγάλες πλάκες από τις οποίες διατηρούνται σε καλή κατάσταση αυτές του νοτίου κλίτους,.
Το ναό ανέσκαψε το 1937 και αναστήλωσε μερικώς ο Α. Ορλάνδος με δαπάνες του Υπουργείου Θρησκευμάτων και Εθνικής Παιδείας και της κοινότητος Αγ. Παρασκευής.