Υπάρχουν δεκάδες τρόποι δημιουργίας σπηλαίων, ανάλογα με το γεωλογικό περιβάλλον της περιοχής. Ωστόσο, η συντριπτική πλειοψηφία των σπηλαίων —συμπεριλαμβανομένου αυτού των Πετραλώνων— απαντά εντός ασβεστολιθικών πετρωμάτων, όπως οι ασβεστόλιθοι, οι δολομίτες και τα μάρμαρα. Το κοινό χαρακτηριστικό αυτών των πετρωμάτων είναι ότι δομούνται από ανθρακικό ασβέστιο (CaCO3), το οποίο είναι ευδιάλυτο στο νερό της βροχής, που εισχωρεί σε προϋπάρχουσες ρωγμές ή ασυνέχειες του πετρώματος και τις διανοίγει, αλλού λιγότερο, αλλού περισσότερο, ανάλογα με την κατά τόπους ανθεκτικότητα του πετρώματος. Με την πάροδο των χιλιετιών και τη συνεχιζόμενη δράση του νερού, τα αρχικά αυτά έγκοιλα συνεχίζουν να μεγαλώνουν, μέχρι να σχηματίσουν —σε ορισμένες περιπτώσεις— δαιδαλώδη υπόγεια συστήματα συνολικού μήκους δεκάδων ή και εκατοντάδων χιλιομέτρων.
Μετά την αρχική διάνοιξη των υπογείων εγκοίλων, και εφ’ όσον υπάρχει σταγονορροή από την οροφή (δηλαδή μικρή παροχή νερού που διέρχεται από ρωγμές), τότε σχηματίζονται δευτερογενείς αποθετικοί σχηματισμοί, αποτελούμενοι από κρυσταλλικό ανθρακικό ασβέστιο: οι σταλακτίτες στην οροφή και οι σταλαγμίτες στο δάπεδο του εγκοίλου. Οι σταλακτίτες και οι σταλαγμίτες είναι συνήθως κωνικοί σχηματισμοί, συχνά όμως μπορεί να έχουν και άλλα σχήματα, όπως πετάσματος, εκτεταμένου σταλαγμιτικού δαπέδου κ.ά., ανάλογα με τις συνθήκες σχηματισμού τους.
Στο δάπεδο των σπηλαίων βρίσκει, ωστόσο, κανείς και άλλα υλικά, που δεν προέρχονται από χημική απόθεση. Τέτοια είναι τα ιζήματα —κυρίως αργιλικά— που συγκεντρώνονται στα χαμηλότερα σημεία του σπηλαίου. Άλλα υλικά μπορεί να είναι ασβεστολιθικά τεμάχη της οροφής, που, χάνοντας τη στήριξή τους με την προοδευτική διεύρυνση του σπηλαίου, καταπίπτουν στο δάπεδο, ή φερτά υλικά προερχόμενα από το εξωτερικό του σπηλαίου, που μεταφέρονται στο εσωτερικό του δια της μηχανικής δράσης του νερού ή της βαρύτητας.
Όταν η διεύρυνση των σπηλαίων προχωρήσει τόσο, ώστε η οροφή να μην μπορεί να στηρίξει το βάρος της, τότε αυτή υποχωρεί και αποκαλύπτεται το εσωτερικό του σπηλαίου. Αυτό μπορεί να οδηγήσει στη διάβρωση του εσωτερικού, λόγω της έκθεσής του στα καιρικά φαινόμενα, και στην πλήρωσή του με φερτά υλικά του περιβάλλοντος. Η συνεχιζόμενη διάβρωση οδηγεί τελικά στην καταστροφή του σπηλαίου, αφήνοντας μόνο λίγα ίχνη του.