Η παράδοση για το παρελθόν της Ηλείας αποτελεί, όπως είναι φυσικό, ένα κράμα από μύθους και ιστορικά γεγονότα.

Περίπου τρεις χιλιάδες χρόνια προ Χριστού , οι Έλληνες κατήλθαν κυρίως από την ξηρά στον Ελλαδικό χώρο, βρίσκοντας εκεί προελληνικό πληθυσμό. Αυτοί οι παλαιότεροι κάτοικοι της Ηλείας ήταν Αχαιοί, και αναμείχθηκαν με τον προελληνικό πληθυσμό της περιοχής, αλλά και με φύλα από τη Θεσσαλία, την Αττική, τη Βοιωτία, την Μικρά Ασία και την Κρήτη.

Παραδίδεται ότι ο πρώτος βασιλιάς της Ηλείας Αέθλιος, γιος του Δία και της Πρωτογένειας, εγκαταστάθηκε στην Ηλεία, φέροντας μαζί του φύλα Θεσσαλών. Η συγγένεια με τους Θεσσαλούς φαίνεται και από την ύπαρξη κοινών τοπωνυμίων σε Ηλεία και Θεσσαλία (Πηνειός, Λάρισος, Ενιπέας κ.λ.π.). Το ίδιο έπραξε και ο γιος του Ενδυμίωνας, ο οποίος άφησε την βασιλεία στον γιο του Επειό, όταν ο τελευταίος νίκησε τους αδελφούς του σε αγώνα δρόμου, τον οποίο διοργάνωσε ο πατέρας τους. Από τον νικητή αυτόν του αγώνα, οι κάτοικοι πήραν την αρχική τους ονομασία, Επειοί. Ο αδερφός του Επειού και διάδοχος του θρόνου Αιτωλός, αναγκάστηκε να φύγει από την Ηλεία, επειδή σε κάποιους αγώνες σκότωσε κατά λάθος τον βασιλιά Άπι. Έφτασε στην Κουρήτιδα χώρα, της οποίας κατέλαβε τον θρόνο. Από αυτόν η χώρα ονομάσθηκε Αιτωλία.

Στην περιοχή της Πίσας ηγεμόνας ήταν ο Οινόμαος, τον οποίο διαδέχθηκε ο λυδός Πέλοπας (συμβολίζει το μεταναστευτικό ρεύμα από την Μ.Ασία) και τότε η Πισάτις αποσχίσθηκε από την χώρα του Επειού.

Στην περιοχή του Επειού βασίλεψε –μετά τον γιο του Αιτωλό- ο ανιψιός του Επειού, ο Ηλείος, από τον οποίο μετονομάσθη η περιοχή Ήλις ή Ηλεία.

Γιος του Ηλείου ήταν ο Αυγέας, που πρωταγωνιστεί στον γνωστό μύθο με τον Ηρακλή.

Κατά την κάθοδο των Δωριέων (1100 π.Χ.) εισβάλουν στην Ηλεία Αιτωλικά φύλα, των οποίων ο αρχηγός καταγόταν όπως αναφέρθηκε πιο πάνω από τους πρώτους βασιλείς της Ήλιδας.

Σύμφωνα λοιπόν με τον Παυσανία, επί της βασιλείας του γιου του Αμφιμάχου, Ηλείου, εισέβαλαν στην Πελοπόννησο οι Δωριείς, με αρχηγούς τους γιους του Αριστομάχου. Ο μύθος παραδίδει ότι πήραν χρησμό από την Πυθία να κάνουν αρχηγό της καθόδου τον «τριόφθαλμο»

Όντας σε απορία για το νόημα του χρησμού συνάντησαν στον δρόμο τους έναν άνδρα, με έναν ημίονο, τυφλό από το ένα μάτι. Αυτός ο άντρας ήταν ο Όξυλος, απόγονος του Αιτωλού, ο οποίος είχε όπως είδαμε παλαιότερα εξορισθεί από την Ηλεία, κατηγορούμενος για φόνο. Αυτός πέρασε τους Δωριείς στην Πελοπόννησο μέσω Αρκαδίας, ώστε να μην δουν τον πλούτο της ηλειακής πεδιάδας, και αυτοί σε ανταμοιβή του παραχώρησαν την Ήλιδα.

Ο Όξυλος επέτρεψε στους Επειούς να διατηρήσουν ό,τι κατείχαν, έφερε όμως και τους Αιτωλούς μαζί του και προχώρησε σε αναδασμό της γης, καλώντας ταυτόχρονα όσους κατοίκους των γύρω περιοχών ήθελαν, να εγκατασταθούν στην Ήλιδα. Ο Όξυλος θάφτηκε στην πύλη του φρουρίου που οδηγούσε προς την Ολυμπία, επειδή υπήρχε χρησμός που ανέφερε ότι δεν έπρεπε να ταφεί ούτε μέσα στην πόλη, ούτε έξω από αυτήν.