Στη θέση της αρχαίας Ποτίδαιας, αποικίας των Κορινθίων στο λαιμό της χερσονήσου της Κασσάνδρας, η οποία καταστράφηκε από τον Φίλιππο το 357 π.Χ., ανίδρυσε ο Κάσσανδρος το 316 π.Χ. μία νέα πόλη, την Κασσάνδρεια. Η ελληνιστική αυτή πόλη εξελίχθηκε σε μία από τις σημαντικότερες πόλεις της Μακεδονίας, γνωρίζοντας μεγάλη άνθηση κατά την ρωμαιοκρατία και τους πρώτους χριστιανικούς αιώνες.

Το 540 μ.Χ. καταστράφηκε από τους Ούννους και ο αυτοκράτορας Ιουστινιανός Α΄ φρόντισε για την ανασύστασή της. Σύμφωνα με τον ιστορικό Προκόπιο, ο Ιουστινιανός, για να προστατέψει την πόλη και όλη τη χερσόνησο από τις βαρβαρικές επιδρομές, οχύρωσε το διατείχισμα που υπήρχε κατά μήκος του λαιμού της χερσονήσου και εκτεινόταν από το Θερμαϊκό ως τον Τορωναίο κόλπο : "το κατά την είσοδο διατείχισμα τοις επιβουλεύειν εθέλουσιν αμαχόν τε και ανανταναγώνιστον διεπράξατο διαφανώς είναι".

Οι επόμενες ιστορικές πληροφορίες που αφορούν στο διατείχισμα προέρχονται από το 15ο αι., όταν ο τέως αυτοκράτορας Ιωάννης Ζ΄ Παλαιολόγος έγινε δεσπότης Θεσσαλονίκης και από το 1403 προχώρησε σε μεγάλης έκτασης ανακατασκευές του τείχους και στη διάνοιξη μίας τάφρου. Μερικά χρόνια αργότερα, το 1424, οι Βενετοί επιχείρησαν νέες επισκευές στο τείχος, οι οποίες όμως φαίνεται ότι δεν ολοκληρώθηκαν.

Τελευταία χρήση του διατειχίσματος με πρόχειρες επισκευές και νέα διάνοιξη της τάφρου συντελείται στην Επανάσταση του 1821, όταν οι Χαλκιδικιώτες αγωνιστές οχυρώνονται σ' αυτή τη θέση, προκειμένου να συγκρατήσουν την επέλαση του Οθωμανικού στρατού.

Η εγκατάσταση προσφύγων από την Ανατολική Θράκη στο σημερινό οικισμό της Νέας Ποτίδαιας που χρησιμοποίησαν οικοδομικό υλικό από το αρχαίο τείχος, στη συνέχεια η διάνοιξη της διώρυγας και αργότερα η κατασκευή της πρώτης γέφυρας επέφεραν μεγάλες καταστροφές στο υπάρχον διατείχισμα, ενώ αλλοίωσαν δραστικά τον περιβάλλοντα χώρο.

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