Στους νότιους πρόποδες του Κρονίου λόφου αναπτύχθηκαν οι προϊστορικές λατρείες του ιερού, όπως του Κρόνου, της Ρέας, της Γαίας, της Θέμιδας, της Ειλειθυίας, του Ιδαίου Ηρακλή και άλλων θεοτήτων. Κατά την Πρωτοελλαδική ΙΙΙ περίοδο (2300-2000 π.Χ.), σύμφωνα με τα μέχρι τώρα ανασκαφικά δεδομένα, φαίνεται ότι είχε διαμορφωθεί στο χώρο της Άλτεως ένα πρωτόγονο οργανωμένο ιερό, ενδεχομένως και κάποιος οικισμός γύρω του, με συνεχή κατοίκηση ως την Υστεροελλαδική ΙΙΙ εποχή (1600-1100 π.Χ.).

Νοτιοανατολικά του Ηραίου έχει ερευνηθεί ένα από τα προϊστορικά κτήρια της Ολυμπίας, το κτήριο ΙΙΙ, το οποίο βρίσκεται σε κατώτερο επίπεδο από τα κτίσματα της αρχαϊκής και κλασικής εποχής. Στην ίδια περιοχή έχουν ερευνηθεί συνολικά έξι προϊστορικά κτίσματα, τα οποία δεν είναι ορατά διότι έχουν καταχωθεί. Το προϊστορικό κτήριο ΙΙΙ της Ολυμπίας έχει προσανατολισμό Β-Ν και αψιδωτή κάτοψη. Από την όλη κατασκευή διατηρείται μόνο μία σειρά από τους ακατέργαστους λίθους των θεμελίων, ενώ η ανωδομή του πρέπει να ήταν από φθαρτά υλικά. Η μελέτη της κεραμικής, που προέρχεται από το κτήριο, έδειξε ότι αυτό χρονολογείται στο τέλος της Πρωτοελλαδικής ΙΙΙ εποχής, μεταξύ του 2150 και 2000 π.Χ., και ότι την περίοδο αυτή ίσως υπήρχαν επαφές με τον πολιτισμό Cetina, που αναπτύχθηκε στις Δαλματικές ακτές. Μαζί με τον προϊστορικό τύμβο που βρίσκεται κάτω από το παρακείμενο Πελόπιο(2500 π.Χ.), τα αψιδωτά κτήρια αποτελούν τις παλαιότερες κατασκευές του ιερού.