Από την εποχή που έπαψε να υφίσταται η έννοια"πόλις-κράτος", οι ανθηρές και εύρωστες αρχαίες πόλεις της Θράκης αρχίζουν σταδιακά να παρακμάζουν, για να οδηγηθούν σε έντονη κάμψη κατά το τέλος της ύστερης αρχαιότητας (4ος - 5ος αι.).

Την ίδια τύχη με τις υπόλοιπες αρχαίες πόλεις της Θράκης είχαν και τα Άβδηρα. Η παρακμή της πόλης αρχίζει από την ελληνιστική εποχή για να υποστεί μεγάλη καταστροφή, όπως ανασκαφικά βεβαιώθηκε, στην εποχή του αυτοκράτορα Κωνσταντίνου Α΄(307-337 μ.Χ.), που σήμανε και το τέλος της αρχαίας πόλης. Από την εποχή αυτή και μετά, η πόλη δεν μνημονεύεται στις γραπτές πηγές για πέντε αιώνες και συγκεκριμένα μέχρι το 879, οπότε και εμφανίζεται ως έδρα επισκοπής με το όνομα Πολύστυλον στα πεπραγμένα της οικουμενικής συνόδου της Κωνσταντινουπόλεως με επίσκοπο τον Δημήτριο. Η μεταλλαγή του ονόματος από Άβδηρα σε Πολύστυλον θα πρέπει να πραγματοποιήθηκε στα πρώτα χρόνια της Μακεδονικής Δυναστείας, εποχή κατά την οποία παρατηρείται ανασυγκρότηση των πόλεων και ανάδειξη πολλών απ' αυτές σε έδρες επισκοπών.

Το καινούργιο όνομα που δόθηκε στην πόλη - Πολύστυλον -προέρχεται από τους πολλούς στύλους (κίονες), που υπήρχαν στον χώρο της αρχαίας πόλης. Σύμφωνα με τις κατά καιρούς εκκλησιαστικές εκθέσεις (Notitiae) η επισκοπή Πολυστύλου υπαγόταν στην μητρόπολη Φιλίππων, για να αποσπαστεί απ' αυτήν λόγω αποστάσεως και να προσαρτηθεί στην αρχιεπισκοπή Μαρωνείας κατά τα έτη 1365-1370. Τελευταίος γνωστός επίσκοπος Πολυστύλου είναι ο Πέτρος, που το 1363 υπογράφει έγγραφο για την κυριότητα του μονυδρίου των αγίων Κωνσταντίνου και Ελένης, που βρισκόταν στη Θάσο.

Πέρα από τις εκκλησιαστικές πηγές η πόλη αναφέρεται συχνά και στους βυζαντινούς συγγραφείς, είτε με το βυζαντινό της όνομα (Πολύστυλον), είτε με το αρχαίο (Άβδηρα). Από τον Γρηγορά χαρακτηρίζεται ως φρούριον και από τον Καντακουζηνό ως πολίχνιον παράλιον. Η πόλη, όπως και ολόκληρη η Θράκη, γνωρίζει κατά τον 14ο αι. τις συνέπειες του εμφυλίου πολέμου (1341-1346), που ξέσπασε στο βυζάντιο ανάμεσα στην Άννα Παλαιολογήνα, χήρα του αυτοκράτορα Ανδρόνικου Γ΄, και τον Ιωάννη Καντακουζηνό. Την πόλη επισκέπτεται το 1342 ο Ιωάννης Καντακουζηνός, κατά τη διάρκεια ταξιδιού του στη Σερβία για αναζήτηση συμμάχων, εφοδιάζοντάς την με σιτάρι και τοποθετώντας φρουρά στο κάστρο της. Την ίδια χρονιά ο αυτοκρατορικός στόλος υπό τον ναύαρχο δούκα Απόκαυκο, εχθρό του Καντακουζηνού, καταπλέει στο λιμάνι της, ενώ την επόμενη χρονιά (1343)αγκυροβολεί εδώ ο στόλος του εμίρη του Αϊδινίου Ομούρ Μπέη, ερχόμενος σε βοήθεια του συμμάχου του, Καντακουζηνού. Για δύο χρόνια (1343-1345) η πόλη βρίσκεται στα χέρια του βούλγαρου ηγεμονίσκου Μομτζίλου, που, εκμεταλλευόμενος τη συμμαχία του με την Άννα Παλαιολογίνα, καταλαμβάνει την Ξάνθεια (Ξάνθη) και καθίσταται πρόσκαιρα κυρίαρχος της περιοχής.

Από τις πληροφορίες των βυζαντινών ιστορικών και χρονογράφων συνάγεται ότι το Πολύστυλον υπήρξε κατά την υστεροβυζαντινή περίοδο μια αρκετά σημαντική οχυρωμένη ναυτική πόλη, που επικοινωνούσε με την ενδοχώρα με δύο δρόμους, από τους ποίους ο ένας οδηγούσε στην Ξάνθεια και ο άλλος στο Περιθεώριον (Αναστασιούπολης). Μετά την κατάληψη της περιοχής από τους Οθωμανούς η πόλη εγκαταλείπεται, για να ιδρυθεί ο μεταβυζαντινός οικισμός σε απόσταση 6 χλμ. Βόρεια, στη θέση του σημερινού οικισμού των Αβδήρων.