Στο δυτικό άκρο του κόλπου της Καβάλας ανοίγεται ο ευρύχωρος όρμος των Ελευθερών, όνομα προερχόμενο από το χωριό Ελευθεραί που βρίσκεται στο βάθος της κοιλάδας. Σήμερα ο προσφυγικός οικισμός της Νέας Περάμου που αναπτύχθηκε κατά μήκος της ακτογραμμής τείνει να δώσει το όνομά του στην περιοχή. Δυτικά της Νέας Περάμου και σε χαμηλό λόφο, οι βόρειες παρυφές του οποίου βρέχονται από τη θάλασσα, υψώνονται τα ερείπια ενός βυζαντινού κάστρου που ταυτίζονται με τη βυζαντινή πόλη Ανακτορόπολη. Η πόλη μνημονεύεται στις πηγές από τον 10ο αι. έως τον 15ο αι. Τον 10ο αι. αναφέρεται με το όνομα Αλεκτρυόπολις, τον 11ο- 13ο αι. ως Αλεκτορόπολις και τον 14ο αι. ως Ανακτορόπολις και Ελευθερόπολις. Οι διαφορετικές αυτές ονομασίες δημιούργησαν σύγχυση στους μελετητές για το εάν πρόκειται για την ίδια πόλη και έκανε τους περισσσότερους ιστιοριοδίφες να αναζητούν τη θέση της από το Νέστο ως το Στρυμόνα. Η ταύτιση της Ανακτορόπολης με τα ερείπια της Νέας Περάμου είναι σήμερα αποδεκτή. Σύμφωνα με τις εκκλησιαστικές πηγές αποτέλεσε επισκοπή της μητρόπολης Φιλίππων μετά την κατάργηση της οποίας πέρασε στη δικαιοδοσία του μητροπολίτη Δράμας, ενώ στους νεώτερους χρόνους αποτέλεσε τη μητρόπολη Ελευθερουπόλεως. Η Ανακτορόπολη φαίνεται να διαδραμάτισε κάποιον ιδιαίτερο λόγο στα ιστορικά δρώμενα κατά τον 14ο αι., οπότε και αναφέρεται αρκετά συχνά στις πηγές. Στα 1350, όπως μας πληροφορεί ο Καντακουζηνός, ήταν υπό την εξουσία ενός Αλέξιου με καταγωγή από τη Βιθυνία, ο οποίος κατά τη διάρκεια του εμφυλίου πολέμου ήταν μισθοφόρος στην υπηρεσία του μεγάλου Δουκός Αλέξιου Απόκαυκου. Πρόκειται για τους αδελφούς Αλέξιο και Ιωάννη οι οποίοι εκμεταλευόμενοι τις δυναστικές έριδες του 14ου αι. έδρασαν στις ακτές του Βορείου Αιγαίου, αρχικά ως μισθοφόροι του αυτοκράτορα και αργότερα για λογαριασμό τους, καταλαμβάνοντας είτε από τους Τούρκους, είτε από τους Σέρβους διάφορα κάστρα στην περιοχή. Στη νότια πλευρά του οχυρωματικού περιβόλου του κάστρου υπάρχει πλίνθινη επιγραφή η οποία διαβάστηκε ως εξής: "ΑΝΔΡΟΝΙΚΟΥ ΚΟΝΤΟΣΤΕΦΑΝΟΥ ΜΕΓΑΛΟΥ ΔΟΥΚΟΣ ΜΙΝΙ ΙΟΥΛΙΩ ΙΣ ΤΑΣ Η΄". Ο Ανδρόνικος Κοντοστέφανος ταυτίζεται με τον Μεγάλο Δούκα Ανδρόνικο Κοντοστέφανο, ανεψιό του αυτοκράτορα Μανουήλ Α΄ (1143-1180). Με βάση την ταύτιση αυτή, η ανέγερση του τοποθετείται στα χρόνια 1167-1170. Κατά μια άλλη άποψη πρόκειται για τον Μεγάλο Δούκα Αλέξιο Απόκαυκο που κατά τη διάρκεια επιχειρήσεων του εμφυλίου πολέμου το 1342 περιέπλευσε με στόλο την ακτή του Βορείου Αιγαίου. Στο πλαίσιο αυτών των επιχειρήσεων προέβη στη ριζική επισκευή ενός κάστρου που έλεγχε ένα από τα λίγα λιμάνια ανάμεσα στη Θεσσαλονίκη και την Κωνσταντινούπολη, τη φύλαξη του οποίου εμπιστεύθηκε στον μισθοφόρο Αλέξιο. Στα 1357 με χρυσόβουλλο του αυτοκράτορα Ιωάννη Ε΄ Παλαιολόγου η Ανακτορόπολη, η Χρυσόπολη και η Θάσος παραχωρήθηκαν με τίτλο κληρονομικότητας στον Αλέξιο που κατείχε πλέον τον τίτλο του μεγάλου πριμηκηρίου και στον αδελφό του Ιωάννη που κατείχε τον τίτλο του πρωτοσεβαστού,. Το κάστρο πρέπει να έπεσε στα χέρια των Οθωμανών μεταξύ 1383 και 1387. Ωστόσο, η επισκοπή Ελευθερουπόλεως παρέμεινε ως όνομα έως και το δεύτερο μισό του 15ου αι., ο οικισμός όμως πρέπει να είχε μεταφερθεί αλλού. Στα τέλη του 18ου αι. αναφέρεται το ορεινό χωριό Ελευθεραί, (Λεφτέρ και Λεφτερόπολη επί Τουρκοκρατίας), σκαρφαλωμένο στους πρόποδες των προβούνων του Συμβόλου Όρους και μακριά από τη θάλασσα. Ενδεχομένως στη θέση αυτή να μεταφέρθηκαν από τον 16ο -17ο αι., όπως συνέβη και σε άλλες βυζαντινές πόλεις (Πολύστυλο, Μαρώνεια, οικισμοί Θάσου), λόγω της πειρατίας που λυμαίνονταν τα παράλια.