Στη θέση Κεφάλα, νότια του χωριού, έχουν βρεθεί τα ερείπια της αρχαίας πόλης Ελύρου, η οποία άκμασε τους ελληνιστικούς και ρωμαϊκούς χρόνους, ούσα η σημαντικότερη πόλη στη νοτιοδυτική Κρήτη. Σήμερα σώζονται λείψανα οικισμών και δεξαμενών και στο νότιο τμήμα της πόλης βρίσκεται το νεκροταφείο της πόλης. Περιηγητές αναφέρουν ότι βρήκαν ερείπια αρχαίου θεάτρου και υδραγωγείου. Η πόλη συνέχισε να υφίσταται και τους βυζαντινούς χρόνους, όταν ήταν έδρα επισκοπής, μέχρι που καταστράφηκε από τους Σαρακηνούς.

Το σημερινό χωριό πιθανόν δημιουργήθηκε τους πρώτους χρόνους των ενετικών χρόνων. Η ονομασία Ροδοβάνι σύμφωνα με τον Δ. Σαλαμάγκα, το όνομα προέρχεται από το όνομα ιταλικό Rodovan το οποίο σημαίνει Ιλλυριός. Ο Στέργιος Σπανάκης επισημαίνει ότι το επίθετο Rodovano αναφέρεται στο δουκικό αρχείο του Χάνδακα από το 1366 και έτσι θεωρεί ότι το χωριό ιδρύθηκε από Κροάτη μισθοφόρο, ο οποίος πιθανόν ήρθε στα πλαίσια καταστολής των επαναστάσεων της Κρήτης.

Στην απογραφή του Φραντσέσκο Μπαρότσι το 1577 αναφέρεται ως Rhodovani. Στην ενετική απογραφή του 1583 από τον Καστροφύλακα απογράφεται μαζί με τα χωριά Αγριλιά και Μονοχριστογέρακο με 280 κατοίκους, ενώ στη συνέχεια αναφέρεται ως Rodovani με 16 οφειλόμενες αγγαρείες. Από τον Φραντσέσκο Βασιλικάτα το 1630 αναφέρεται το Rodhovani. Στην απογραφή η οποία πραγματοποιήθηκε από τους Αιγυπτίους το 1834 αναφέρεται ως Rodhovani με κυρίως χριστιανικό πληθυσμό, 30 οικογένειες, ενώ αναφέρεται και μια μουσουλμανική.