Το βυζαντινό φρούριο του Παλαιού Γυναικόκαστρου βρίσκεται 12χλμ ΝΔ της πόλης του Κιλκίς, καταλαμβάνει έκταση περίπου 25 στρεμμάτων και σε κάτοψη έχει σχήμα τραπεζίου. Περιβάλλεται από ισχυρά εξωτερικά τείχη, θεμελιωμένα απευθείας στον φυσικό βράχο, με περίμετρο 614 μ., τα οποία σώζονται σήμερα σε ύψος κυμαινόμενο από 5,0 έως 8,0 μ. Η τοιχοδομία τους είναι από αργολιθοδομή με σποραδικές πλίνθους και ασβεστοκονίαμα ως συνδετικό υλικό.
Υπήρξε ισχυρός προμαχώνας της συμβασιλεύουσας Θεσσαλονίκης και ιδρύθηκε από τον αυτοκράτορα Ανδρόνικο Γ΄ Παλαιολόγο, μεταξύ των ετών 1328-1341.
Η ονομασία του, σύμφωνα με τον Βυζαντινό Αυτοκράτορα Ιωάννη Καντακουζηνό, οφείλεται στα ισχυρά του τείχη, που καθιστούσαν δυνατή την υπεράσπισή του ακόμη και από γυναίκες.
Το φρούριο καταλήφθηκε, όπως και ο υπόλοιπος μακεδονικός χώρος, από τους Οθωμανούς περί το 1383-1389. Η λαϊκή παράδοση κατέγραψε τον μύθο της εκπόρθησής του στην ιστορία της Μαρουλίας, της γυναίκας του διοικητή, που έπεσε μαχόμενη, υπερασπίζοντας το κάστρο.
