Για πρώτη φορά το όνομα του χωριού συναντιέται σε συμβολαιογραφικά έγγραφα του 13ου αιώνα και σε κατοπινά του Δουκικού Αρχείου του Χάνδακα. Καταγράφεται με το ίδιο περίπου σημερινό του όνομα (Petrokefalo ή Petrokefala) σε όλες τις απογραφές από το 1577 μέχρι και σήμερα.
Η ιδιαιτερότητα του σχήματος του λόφου πάνω στον οποίο είναι χτισμένο (έχει τη μορφή ανθρώπινου κεφαλιού), θεωρείται ότι έδωσε ονομασία του χωριού, ή κατ’ άλλη εκδοχή, ο οικισμός ονομάστηκε έτσι από τον πρώτο οικιστή του, Πέτρο, ιδιοκτήτη του λόφου.
Το χωριό υπέστη την οργή του Εγκέλαδου το 1856 (όπως και πολλά άλλα χωριά της περιφέρειας) και καταστράφηκε ολοσχερώς, χάνοντας την όμορφη παλαιότερη παραδοσιακή αρχιτεκτονική του. Γρήγορα ανοικοδομήθηκε με νεότερα βέβαια κτίσματα που παρουσιάζουν πολύ ενδιαφέροντα αρχιτεκτονικά στοιχεία του 19ου αιώνα (οικία Κρασαδάκη).
Στα καταλύματα «Agioklima Studios» (παλιό παραδοσιακό σπίτι, με πλήρεις εγκαταστάσεις), σας εξασφαλίζουν άνετη και ευχάριστη διαμονή, ενώ στο Κέντρο εστίασης και στο καφενείο του χωριού μπορείτε να απολαύσετε γραφικές παραδοσιακές στιγμές γευσιποσίας και αναψυχής.
Πολιούχος του χωριού είναι ο ναός της Παναγίας που γιορτάζει στις 8 Σεπτεμβρίου οπότε οργανώνεται πανηγύρι με καλό παραδοσιακό γλέντι από τον Μορφωτικό Σύλλογο του χωριού, ο οποίος αναπτύσσει και διάφορες άλλες πολιτιστικές δράσεις.
Χαρακτηριστικό του οικισμού είναι τα σαφή χαρακτηριστικά οχυρωματικού (φρουριακού) τύπου . Σε ανασκαφές της δεκαετίας του 70 που διενεργήθηκαν στην περιοχή βρέθηκαν: ένας λαξευτός τάφος με λουτροειδή λάρνακα, μία σαρκοφάγος και ταφικοί πίθοι.
