Τα σπήλαια ανέκαθεν λειτουργούσαν ως χώροι καταφυγίου και προστασίας για πολλά ζώα, ιδιαιτέρως δε για τα σαρκοφάγα, τα οποία τα χρησιμοποιούν ως φωλιές. Εκεί φέρνουν μέρος της λείας τους, ώστε να την καταναλώσουν με ασφάλεια, μεγαλώνουν τα μικρά τους, και —ορισμένα, όπως οι αρκούδες— διαχειμάζουν σε κατάσταση νάρκης. Τα υπολείμματα της τροφής τους, καθώς και τα ίδια τα σαρκοφάγα κάθε ηλικίας που θα τύχει να πεθάνουν εντός του σπηλαίου, συσσωρεύονται με το πέρασμα των αιώνων και σκεπάζονται σταδιακά από τα ιζήματα που αποτίθενται στο δάπεδο του σπηλαίου. Τα θαμμένα οστέινα κατάλοιπα προστατεύονται από την καταστροφή και, αν οι συνθήκες είναι κατάλληλες, μπορεί να απολιθωθούν με την πάροδο μερικών χιλιάδων ετών.
Τι είναι όμως τα απολιθώματα; Πρόκειται για λείψανα οργανισμών του παρελθόντος που διατηρούνται έως σήμερα εντός των πετρωμάτων. Συνήθως διατηρούνται μόνο τα σκληρά μέρη, όπως τα όστρακα, τα οστά και τα δόντια, τα οποία χάνουν τα οργανικά τους συστατικά και εμπλουτίζονται με ανόργανες ενώσεις του περιβάλλοντος.
Επίσης συχνά διατηρούνται ίχνη που άφησαν οργανισμοί του παρελθόντος, τα οποία ονομάζονται ιχνοαπολιθώματα. Συνήθως τα βρίσκουμε επάνω σε άλλους οργανισμούς (π.χ. ίχνη δοντιών σε οστά, οπές σε όστρακα κλπ.) ή στο τότε έδαφος (π.χ. ίχνη κινήσεως, αποτυπώματα). Ιχνοαπολιθώματα αποτελούν επίσης τα απολιθωμένα απεκκρίματα ζωικών οργανισμών, τα οποία ονομάζονται κοπρόλιθοι (ή γαστρόλιθοι, όταν προέρχονται από το ανώτερο πεπτικό σύστημα). Συνήθως οι κοπρόλιθοι προέρχονται από θηλαστικά που καταναλώνουν μεγάλες ποσότητες οστών, όπως οι ύαινες.
Το Σπήλαιο Πετραλώνων είναι πολύ πλούσιο σε απολιθώματα: Από την εποχή της ανακάλυψής του έως σήμερα έχουν ανασκαφεί εδώ χιλιάδες απολιθωμάτων που ανήκουν κυρίως σε θηλαστικά, αλλά και σε αμφίβια, ερπετά και πτηνά. Συνολικά έχουν προσδιοριστεί περισσότερα από 50 είδη. Τα πλέον συχνά και εντυπωσιακά είναι οι αρκούδες των σπηλαίων και οι στικτές ύαινες. Αυτά τα είδη χρησιμοποίησαν το σπήλαιο ως χειμερινό καταφύγιο και φωλεά, αντιστοίχως. Τα φυτοφάγα θηλαστικά αντιπροσωπεύονται κυρίως από ίππους, αιγάγρους και ελαφοειδή. Τα οστά τους κατέληγαν στο σπήλαιο συνήθως ως λεία υαινών. Ορισμένα πάντως φέρουν χαραγές από αιχμηρά εργαλεία και ίχνη κτυπήματος, υποδεικνύοντας ότι αποτέλεσαν τροφή του Παλαιολιθικού ανθρώπου. Αυτά τα ευρήματα αποτελούν αρχαιολογικά κατάλοιπα, τα οποία μας δίνουν πολύτιμες πληροφορίες για τα ζώα που κυνηγούσαν οι εκάστοτε ένοικοι του σπηλαίου, αλλά και για τον τρόπο τεμαχισμού και διαχείρισης των θηραμάτων.
Τα κυριώτερα σαρκοφάγα που απαντούν μεταξύ των απολιθωμάτων του Σπηλαίου των Πετραλώνων είναι:
Οι αρκούδες των σπηλαίων είναι μια ομάδα ειδών αρκούδας του Πλειστοκαίνου που χαρακτηρίζονται από πολύ μεγάλο μέγεθος και πολύ εύρωστο σώμα. Παρά τη φοβερή τους εμφάνιση, έχει ωστόσο τεκμηριωθεί (βάσει χημικών αναλύσεων του σκελετού τους) ότι ήταν σχεδόν αποκλειστικώς φυτοφάγες. Λόγω της συνήθειάς τους να χρησιμοποιούν τα σπήλαια ως τόπους χειμερίας νάρκης, απολιθώματά τους έχουν ανακαλυφθεί σε χιλιάδες σπήλαια της Ευρώπης. Τα απολιθώματα αυτά ανήκουν σε άτομα όλων των ηλικιών, από νεογέννητα έως ηλικιωμένα.
Οι στικτές ύαινες του Σπηλαίου των Πετραλώνων είναι στενοί συγγενείς των στικτών υαινών που ζουν σήμερα στην Αφρική, ήταν όμως γενικά μεγαλύτερες σε μέγεθος. Πρόκειται για σαρκοφάγα ζώα που κυνηγούν μεγάλα φυτοφάγα, ή τρέφονται με υπολείμματα κυνηγιού άλλων θηρευτών. Χαρακτηρίζονται από πολύ ισχυρή οδοντοστοιχία, ικανή να θρυμματίζει κόκκαλα. Οι στικτές ύαινες συνήθως μεταφέρουν την τροφή τους στο καταφύγιό τους, συγκεντρώνοντας με την πάροδο του χρόνου μεγάλες ποσότητες κατακερματισμένων οστών με χαρακτηριστικά σημάδια από τα δόντια τους. Το Σπήλαιο Πετραλώνων λειτούργησε για μεγάλα χρονικά διαστήματα ως καταφύγιο/φωλιά υαινών.
Ο λύκος είναι επίσης αρκετά συχνός μεταξύ των απολιθωμάτων του σπηλαίου. Είναι μικρόσωμος σχετικά με τον σημερινό λύκο της Ευρώπης, αλλά μορφολογικώς όμοιος με αυτόν. Πρόκειται για σαρκοφάγο που κυνηγούσε μεσαίου μεγέθους θηράματα. Στην πανίδα των Πετραλώνων απαντά επίσης ένα πιο σπάνιο είδος λύκου, το οποίο συγγενεύει πιθανώς με το σημερινό ασιατικό είδος Cuon alpinus, καθώς και μία αλεπού. Ένα ακόμη μικρό σαρκοφάγο είναι ο ασβός.
Τα αιλουροειδή είναι πιο σπάνια μεταξύ των απολιθωμάτων του Σπηλαίου Πετραλώνων, αλλά αντιπροσωπεύονται από πέντε είδη, μεταξύ αυτών το λιοντάρι των σπηλαίων (πολύ μεγαλόσωμος συγγενής του σημερινού είδους), η λεοπάρδαλη, καθώς και ένας μαχαιρόδοντας (μεγάλο αιλουροειδές με πολύ ανεπτυγμένους κυνόδοντες στην άνω γνάθο).
Τα μεγάλα φυτοφάγα θηλαστικά που απαντούν ως απολιθώματα στο σπήλαιο Πετραλώνων αντιπροσωπεύονται κατά κύριο λόγο από ίππους και αιγάγρους, που αποτελούν το μεγαλύτερο μέρος των απολιθωμάτων. Οι ίπποι διακρίνονται σε δύο είδη, ένα μεγαλόσωμο και ένα πιο μικρόσωμο, που μοιάζει με όναγρο. Οι αίγαγροι είναι στενοί συγγενείς των σημερινών αιγάγρων των Άλπεων. Συχνά είναι επίσης τα απολιθώματα ελαφοειδών, τα οποία ανήκουν σε τρία είδη διαφορετικών μεγεθών: το πλατώνι, το ελάφι και τον μεγαλόκερο (γιγαντιαίο ελαφοειδές, το οποίο δεν ζει σήμερα). Τα μεγαλόσωμα βοοειδή (ταύρος, βίσωνας) είναι πιο σπάνια, όπως επίσης ο ρινόκερος και ο χοίρος. Τέλος, σποραδικά ευρήματα μεγάλων διαστάσεων μαρτυρούν την παρουσία ελεφάντων.
Η αφθονία ίππων μαρτυρά ανοιχτό περιβάλλον και σχετικά ξηρό κλίμα. Ωστόσο η ύπαρξη τριών ειδών ελαφοειδών, καθώς και χοίρου, δηλαδή θηλαστικών που προτιμούν περιβάλλοντα με σχετικά πυκνή φυτοκάλυψη, υποδηλώνει την ύπαρξη και δασικών εκτάσεων γύρω από το σπήλαιο. Τέλος, η έντονη παρουσία αιγάγρων οφείλεται στην ύπαρξη βραχώδους αναγλύφου στο όρος Κατσίκα.
Τα ζώα μικρού μεγέθους που απαντούν στην απολιθωμένη πανίδα του σπηλαίου ανήκουν σε μεγάλη ποικιλία ειδών αμφιβίων, ερπετών, πτηνών και μικρών θηλαστικών (εντομοφάγων, νυκτερίδων, τρωκτικών και λαγομόρφων).