Στα δυτικά της Νέας Περάμου, σε ένα λόφο, συναντά κανείς τα απομεινάρια ενός κάστρου βυζαντινής αρχιτεκτονικής, που αποτελούσαν κατά πολλούς τη βυζαντινή πόλη Ανακτορόπολη, στην οποία γίνεται ιστορική αναφορά από το 10^ο έως το 15^ο αιώνα. Η δημιουργία του κάστρου έλαβε χώρα, σύμφωνα με τα υπάρχοντα δεδομένα, κατά την περίοδο 1167-1170 και εξασφάλιζε τον έλεγχο ενός λιμανιού ανάμεσα στη Θεσσαλονίκη και την Κωνσταντινούπολη. Με την κατάληψη του κάστρου από τους Οθωμανούς έγιναν κάποιες αλλαγές, ενώ ο οικισμός μετατοπίστηκε από το 16^ο έως το 17^ο αιώνα στο χωριό Ελευθερές, όπου και βρίσκεται σήμερα το κάστρο, για να αναχαιτιστούν οι απειλές από τις επιδρομές των πειρατών.