Το επιβλητικό οικοδομικό συγκρότημα του Γυμνασίου-Σταδίου αναπτύχθηκε κοντά στο νότιο τείχος της πόλης κατά τους ελληνιστικούς έως και τους ύστερους ρωμαϊκούς χρόνους (3ος αι. π.Χ.- 4ος αι. μ.Χ.). Στα δυτικά, ευρεία κάθετη οδός οδηγούσε από το Ασκληπιείο στο μνημειακό πρόπυλο του Γυμνασίου. Tρεις δωρικές στοές και η παλαίστρα περιέκλειαν το στάδιο. Μαρμάρινα αγάλματα θεών και ηρώων και χάλκινοι ανδριάντες γυμνασιαρχών, ευεργετών και πνευματικών ανδρών της πόλης κοσμούσαν το συγκρότημα.

Το τέμενος του Ηρακλή και το βάθρο του Θησέα πίσω από τη δυτική στοά και ιδιαίτερης αρχιτεκτονικής μορφής ταφικά μνημεία εξεχουσών προσωπικοτήτων και αριστοκρατικών οικογενειών της πόλης που τιμώνταν ως ήρωες, συνομιλούσαν με τις λοιπές εγκαταστάσεις για την άσκηση του σώματος και την καλλιέργεια του πνεύματος. Στη δυτική πτέρυγα ξεχωρίζουν η παλαίστρα με το λουτρό της, το δωρικό πρόπυλο του Γυμνασίου και το ταφικό μνημείο Κ3 με την ασυνήθιστη κωνική στέγη. Αμέσως νότια του Σταδίου, δεσπόζει το Μαυσωλείο των Σαιθιδών, σε μορφή δωρικού τετρακιόνιου πρόστυλου ναού. Στην ανατολική πλευρά του σταδίου βρίσκεται το μνημείο των ασπίδων προς τιμή πεσόντων σε μάχη και ο δωρικός κίονας που έφερε αδριάντα, πιθανόν του Αριστομένη. Μεταξύ μνημείων για θεούς, ήρωες και νεκρούς οι Μεσσήνιοι έφηβοι διατελούσαν την τριετή θητεία τους προετοιμαζόμενοι σταδιακά για την μυητική μετάβασή τους στην τάξη των ενάρετων ανδρών.