Τα εντυπωσιακά τείχη της Μεσσήνης περιγράφηκαν από τον περιηγητή Παυσανία ως ισχυρότερα από τα τείχη στη Βαβυλώνα και στα περσικά Σούσα. Περιέβαλαν όχι μόνο την πόλη αλλά ολόκληρη την κοιλάδα. Το μήκος τους έφθανε τα εννέα χιλιόμετρα. Κατασκευάστηκαν με λιθοπλίνθους που προέρχονται από λατομεία στις πλαγιές της Ιθώμης και της Εύας. Οι πύργοι τους είναι τετράγωνοι ή στρογγυλοί και διώροφοι.

Στα ανατολικά η Λακωνική Πύλη οδηγούσε στη Σπάρτη, ενώ στα δυτικά η Αρκαδική Πύλη στη Μεγαλόπολη. Η κάτοψη της Αρκαδικής Πύλης είναι κυκλική, πλαισιώνεται από δύο τετράγωνους πύργους και διέθετε δύο εισόδους, μία εσωτερική και μία εξωτερική. Εξωτερικά της πύλης αποκαλύφθηκαν τάφοι και ταφικά μνημεία.