O βυζαντινός οικισμός του Πολυστύλου καταλαμβάνει μικρό τμήμα της αρχαίας πόλης των Αβδήρων. Περιορίζεται στο χαμηλό παραθαλάσσιο γήλοφο, όπου ήταν η ακρόπολη της αρχαίας πόλης και οριοθετείται από δικό της περίβολο. H βυζαντινή οχύρωση ακολουθεί σε γενικές γραμμές το περίγραμμα του λόφου. H περίμετρός της υπολογίζεται σε 800 μ. και θεμελιώνεται είτε επάνω στο βράχο ή επάνω στο αρχαιότερο τείχος. Tο πάχος της ποικίλλει από 2,40 μ. έως 3,50 μ., ανάλογα με το αν το τείχος είναι απλό, όπως συμβαίνει στη βόρεια και νότια πλευρά ή διπλό, όπως συμβαίνει στη βορειοδυτική πλευρά. Κατά τόπους ενισχύεται με τετράγωνους πύργους, ενώ η βορειοδυτική πλευρά της οχύρωσης, που ήταν και πιο ευάλωτη, ενισχύεται με προτείχισμα. Δύο πύλες στη βόρεια πλευρά και μια μικρή πυλίδα στη δυτική εξασφάλιζαν την επικοινωνία της πόλης με τον έξω χώρο.

H περιμετρική οχύρωση τέμνεται εγκάρσια από δύο εσωτερικά τείχη, από τα οποία το ένα χωρίζει την πόλη σε δύο σχεδόν ίσα τμήματα, ενώ το δεύτερο μαζί με το ανατολικό εξωτερικό τείχος σχηματίζουν τη βυζαντινή ακρόπολη, ενισχυμένη με δύο πύργους που χρονολογούνται στα χρόνια του Ιωάννη Καντακουζηνού. Οι ανασκαφικές έρευνες των τελευταίων ετών αποκάλυψαν κτίσματα της βυζαντινής εποχής, που σχετίζονται με τη θρησκευτική και δημόσια ζωή της πόλης. Ένα από τα δημόσια κτήρια αποκαλύφθηκε στη δυτική πλευρά του οχυρωματικού περιβόλου. Πρόκειται για λουτρώνα, ορθογώνιο σε κάτοψη, με τρεις συνεχόμενους χώρους, από τους οποίους ο μεσαίος ήταν ο θερμαινόμενος. Κοντά στην κεντρική πύλη της βόρειας πλευράς αποκαλύφθηκε μονόχωρος ναός με τρούλο, που στηρίζεται σε τέσσερα αβαθή τόξα. Γύρω του είχε αναπτυχθεί νεκροταφείο με απλούς κιβωτιόσχημους τάφους και χρήση ξύλινων φερέτρων. Ο ναός χρονολογείται στον 12ο αι. και η καταστροφή του τοποθετείται στο 14ο αι.

Στο μεσαίο τμήμα του οικισμού, που αποτελεί και το ψηλότερο σημείο του, ανασκάφηκε ο επισκοπικός ναός. Πρόκειται για τρίκλιτη μεσοβυζαντινή βασιλική που αποτελείται από ανοικτή στοά, νάρθηκα, κυρίως ναό, που διαιρείται σε κλίτη με ισχυρούς πεσσούς, και ιερό. Το δάπεδο αποτελείτο από ανισομεγέθεις μαρμάρινες πλάκες και κάτω από αυτό βρέθηκαν τάφοι σύγχρονοι ή και μεταγενέστεροι του ναού. Στη βορειοδυτική γωνία του ναού προσκολλάται ένα τετράγωνο δωμάτιο που ερμηνεύθηκε ως επισκοπείο. Η ίδρυση του επισκοπικού ναού ανάγεται στον 9ο αι. και η καταστροφή του στα μέσα του 14ου αι. Ο ναός θεμελιώθηκε πάνω στα ερείπια παλαιότερης τρίκλιτης βασιλικής, τμήματα της οποίας είναι ορατά στο κεντρικό και νότιο κλίτος. Σε αυτήν ανήκει και το προσαρτημένο στη βοριοανατολική γωνία του επισκοπικού ναού βαπτιστήριο με οκταγωνικό σχήμα και κτιστή κολυμβήθρα στο σχήμα του σταυρού στο εσωτερικό του. Μεταξύ του βαπτιστηρίου και του επισκοπείου διαμορφώθηκε ανοικτή στοά με ταφική χρήση. Δύο κτιστοί τάφοι σε επαφή με το βόρειο τοίχο του ναού θεωρήθηκε ότι ανήκουν σε σημαίνοντα πρόσωπα. Στην ίδια πλευρά βρέθηκε ζωγραφιστός ένσταυρος ρόδακας, που χρονολογείται στα τέλη του 11ου- αρχές 12ου αι. και σήμερα εκτίθεται στο Αρχαιολογικό Μουσείο των Αβδήρων. Γύρω από το ναό ανασκάφηκαν τμήματα οικιών, ενώ έχουν εντοπισθεί και άλλα κτήρια, τα οποία, όμως, δεν έχουν ακόμα ερευνηθεί.

Βόρεια της ακρόπολης, έξω από τα τείχη και κοντά στη δυτική πύλη της κλασικής οχύρωσης των Αβδήρων, έχουν βρεθεί λείψανα του παλαιότερου νεκροταφείου της βυζαντινής πόλης, που χρονολογείται πριν από τον 9ο αι. μ.Χ. Είναι ορατοί αρκετοί από τους τάφους του, κυρίως κιβωτιόσχημοι, καθώς και η κοιμητηριακή τρίκλιτη βασιλική, που παρουσιάζει τέσσερις περιόδους λειτουργίας.