Η ιστορία του σταδίου ξεκινάει το 1931, 25 ολόκληρα χρόνια πριν τη θεμελίωσή του. Στις 4 Νοεμβρίου του 1931, ο Λυσίμαχος Καυτανζόγλου, διακεκριμένος διπλωμάτης και νομικός, συντάσσει τη διαθήκη του, στην οποία αφήνει όλη την περιουσία του για την ανέγερση στην Θεσσαλονίκη Πανελληνίου Ηρώου για τους αγωνισθέντες για την ελευθερία, από την άλωση της Κωνσταντινούπολης και μεταγενέστερα. Ανάμεσα στους ήρωες αυτούς ήταν και ο παππούς του Λυσίμαχου Καυτανζόγλου, Ιωάννης Γούτας Καυτανζόγλου, μέλος και χρηματοδότης της Φιλικής Εταιρίας. Η απόφαση αυτή του Λυσίμαχου Καυτανζόγλου έμελλε να οδηγήσει στην ανέγερση του Σταδίου, αφού θεωρήθηκε ότι η πόλη της Θεσσαλονίκης είχε μεγαλύτερη ανάγκη από σύγχρονες αθλητικές υποδομές. Στην απόφαση αυτή είχαν πρωτοστατήσει ο τότε πρωθυπουργός της Ελλάδας Κωνσταντίνος Καραμανλής και ο Θεσσαλονικιός εκδότης και πολιτευτής Πέτρος Λεβαντής. Για να τηρηθεί όμως το πνεύμα της διαθήκης του ευεργέτη αποφασίστηκε να αναγερθούν στον χώρο του σταδίου προτομές της οικογένειας Καυτανζόγλου.

Έτσι, με νομοθετικό διάταγμα του 1956 ορίζεται ότι η περιουσία του Ιδρύματος Λυσίμαχου Καυτανζόγλου θα διατεθεί για την ανέγερση σταδίου. Τα κονδύλια που διατέθηκαν από το ίδρυμα Λυσίμαχου Καυτανζόγλου ανέρχονταν στα 22 εκατομμύρια δραχμές, ποσό τεράστιο για την εποχή εκείνη. Άλλα 14 εκατομμύρια διέθεσε η Γενική Γραμματεία Αθλητισμού, ενώ παραχωρήθηκαν 24,5 στρέμματα γης από τον Δήμο Θεσσαλονίκης και άλλα 85 από το Ελληνικό Δημόσιο.

Η θεμελίωση του σταδίου έγινε στις 26 Οκτωβρίου 1956, ημέρα εορτασμού της απελευθέρωσης της πόλης και της μνήμης του πολιούχου της, του Αγίου Δημητρίου. Οι εργασίες ολοκληρώθηκαν με γρήγορο ρυθμό και έτσι σε τέσσερα χρόνια και μία ημέρα, στις 27 Οκτωβρίου του 1960, εγκαινιάστηκε το, κατάμεστο από 40.000 θεατές, στάδιο.