Η παλαίστρα βρίσκεται δυτικά της Άλτεως, έξω από τον ιερό περίβολο και πολύ κοντά στον ποταμό Κλαδέο. Οικοδομήθηκε κατά τον 3ο αι. π.Χ. νότια του γυμνασίου και ανήκει στο ίδιο συγκρότημα με αυτό. Χρησίμευε για την προπόνηση των αθλητών στην πυγμή, στην πάλη και στο άλμα.

Πρόκειται για σχεδόν τετράγωνο κτήριο, διαστάσεων 66,35 x 66,75 μ., κτισμένο σε χαμηλότερο επίπεδο, περίπου 0,70 μ. από το γυμνάσιο. Στο κέντρο του βρίσκεται μία υπαίθρια περίστυλη αυλή, στρωμένη με λεπτή άμμο, που ήταν ο χώρος προπόνησης των αθλητών. Η κιονοστοιχία της αποτελείται συνολικά από 72 δωρικούς κίονες και κάθε πλευρά της είχε μήκος 41 μ. Οι κίονες και το κατώτερο τμήμα των τοίχων ήταν λίθινα, ενώ η ανωδομή των τοίχων ήταν πλινθόκτιστη και ο θριγκός ξύλινος. Γύρω από την αυλή αναπτύσσονταν στεγασμένα δωμάτια διαφόρων διαστάσεων, που χρησιμοποιούσαν οι αθλητές πριν και μετά την προπόνησή τους. Η θύρα τους άνοιγε προς την αυλή και τα περισσότερα είχαν στην πρόσοψη ιωνικούς κίονες. Ιωνική κιονοστοιχία υπήρχε και στην πρόσοψη του μεγάλου στενόμακρου χώρου, που καταλάμβανε σχεδόν ολόκληρη τη νότια πλευρά του κτηρίου. Στο εσωτερικό των δωματίων, κατά μήκος των τοίχων υπήρχαν πάγκοι, που εξυπηρετούσαν τη διδασκαλία ρητόρων και φιλοσόφων. Τα δωμάτια χρησίμευαν ως ελαιοθέσιον (χώρος όπου οι αθλητές άλειφαν το σώμα τους με λάδι), ως κονιστήριον (δωμάτιο όπου οι αθλητές έριχναν σκόνη στο σώμα τους), ως αποδυτήρια και λουτρά. Αρχικά η παλαίστρα είχε δύο εισόδους στη νότια πλευρά της. Αργότερα στη βορειοδυτική γωνία της κτίσθηκε ένα πρόπυλο με τέσσερις δωρικούς κίονες στην πρόσοψη. Αυτή έγινε και η κύρια είσοδος στο κτήριο, ενώ η επικοινωνία με το παρακείμενο γυμνάσιο γινόταν μέσω μιας μικρής θύρας που υπήρχε στο μέσον περίπου του βόρειου τοίχου της παλαίστρας και οδηγούσε στη νότια στοά του γυμνασίου.

Η παλαίστρα αποκαλύφθηκε και ερευνήθηκε κατά τις νεότερες γερμανικές ανασκαφές. Από το μνημείο σώζονται μόνο τα κατώτερα, λίθινα τμήματα, ενώ έχουν αναστηλωθεί οι 32 από τους 72 κίονες του εσωτερικού περιστυλίου της αυλής.