Η ονομασία του οφείλεται σε έναν μεγάλο αριθμό αρχαίων μαρμάρινων στύλων (κιόνων), που βρέθηκαν στη περιοχή και πλέον βρίσκονται στο προαύλιο της εκκλησίας του χωριού. Ευρήματα αποδεικνύουν, ότι έχει κατοικηθεί ήδη από αρχαιοτάτων χρόνων. Τον 19ο αιώνα στην περιοχή υπήρχε μεγάλο κτήμα γνωστό ως κτήμα της Μπουλούτσκας ή Μπουλούστρας, όπου κατοικούσαν οι εργάτες του, πιθανότατα ελληνικής καταγωγής.<ref>{{cite web | url=http://protovouliafilippon.blogspot.com/2018/09/1970-2018.html?m=1 | accessdate=20 Νοεμβρίου 2018}}</ref> Σύμφωνα με τη στατιστική Κατσόμπα του 1900 στην Μπουλούστρα κατοικούσανεργάζονταν 45 τσιγγάνοι.<ref>{{cite web | url=http://www.lithoksou.net/p/perioxi-kabalas | title=Ο πληθυσμός της περιοχής Καβάλας | publisher=Δημήτρης Λιθοξόου | accessdate=7 Φεβρουαρίου 2017}}</ref> Μετά την ανταλλαγή πληθυσμών, στο Πολύστυλο εγκαταστάθηκαν 49 οικογένειες προσφύγων.<ref>{{cite web | url=http://www.lithoksou.net/p/egkatastasi-prosfygon-grafeio-kabalas | title=Εγκατάσταση προσφύγων - Γραφείο Καβάλας (Καβάλλας) | publisher=Δημήτρης Λιθοξόου | accessdate=7 Φεβρουαρίου 2017}}</ref> Πρόκειται, δηλαδή, για έναν καθαρά προσφυγικό οικισμό, κυρίως Θρακιωτών. Με το [[πρόγραμμα Καποδίστριας]] εντάχθηκε στο δήμο Φιλίππων και παλαιότερα υπαγόταν στην κοινότητα [[Αμυγδαλεώνας|Αμυγδαλεώνος]], μέχρι το 1949, όταν και αποσπάστηκε από την κοινότητα αυτή και υπάχθηκε στην κοινότητα Πολύστυλο, της οποίας ορίστηκε έδρα.<ref name="eetaa">{{cite web | url=https://www.eetaa.gr/index.php?tag=oikmet_details&id=18268 | title=Πολύστυλον (Καβάλας) | publisher=ΕΕΤΑΑ | work=Διοικητικές μεταβολές οικισμών | accessdate=7 Φεβρουαρίου 2017}}</ref>
