Το χωριό του Προφήτη Ηλία βρίσκεται 20 χιλιόμετρα νότια από το Ηράκλειο κι έχει ένα λόφο από πάνω του με δύο κορυφές (Ρόκα), όπου βρίσκεται η ακρόπολη της αρχαίας Λύκαστου. Ο Νικηφόρος Φωκάς έχτισε το βυζαντινό κάστρο Τέμενος στην ίδια περιοχή το 961, όταν απελευθέρωσε το νησί από τους Σαρακηνούς. Είχε σκοπό να μεταφέρει την πόλη του Χάντακα (Ηράκλειο) στο κάστρο Τέμενος, αλλά κάτι τέτοιο δεν πραγματοποιήθηκε και η πόλη παρέμεινε στη θέση της. Κατά τον 13ο αιώνα το κάστρο κυριεύτηκε από το Γιενοβέζο Pescatore κι αργότερα από τους Βενετούς. Το όνομα Κανλί Καστέλι στα τουρκικά σημαίνει αιματοβαμμένο κάστρο και πήρε το όνομά του από την αιματοχυσία των Τούρκων από τους Βενετούς και τους Ελληνες το 1647.