Κουδουμαλιά είναι ένα από τα πιο παλιά και μικρά χωριά του Οροπεδίου Λασιθίου και μαζί με τον Μαγουλά και τον Άγιο Χαράλαμπο είναι τα πιο ψηλά χωριά σε υψόμετρο. Το όνομα του χωριού προέρχεται από το μεσογειακό καρποφόρο δέντρο Κράταιγος ο αζαρόλος, κοινώς Κουδούμαλος (που είναι πιο γνωστό ως Αντρικοκιά) που αφθονούσε από τότε στην περιοχή που είναι χτισμένο το χωριό.
Από την Κουδουμαλιά καταγόταν ο Χαΐνης Βισκαδούρος που ήταν ένας από τους επαναστάτες του Οροπεδίου επί Τουρκοκρατίας και άνηκε στην ομάδα του Μανώλη Καζάνη.
Επί Κρητικής Πολιτείας η Κουδουμαλιά υπαγόταν στον δήμο Ψυχρού. Εκείνη την περίοδο ο δήμαρχος της περιοχής ήταν από την Κουδουμαλιά και ονομαζόταν Μανώλης Παπαδάκης. Ήταν στο αξίωμα πάνω από 15 χρόνια και είχε διατελέσει σπουδαίο έργο στην περιοχή αν συνυπολογίσουμε ότι δεν είχε γραμματικές γνώσεις και ότι τότε οι δήμοι δεν είχαν καθόλου έσοδα.
Η Κουδουμαλιά αναφέρεται πρώτη φορά από τον Καστροφύλακα (Κ104) Mettocchio Cudhumaglia ,με 5 οικίες και 10 κατοίκους ,το 1583. Αναφέρεται και από τον Βασιλικάτα (Μνημεία Κρητ. Ιστ. V, σ.28) Cudumaglia το 1630. Στην τουρκική απογραφή που έγινε στα 1671 δεν αναφέρεται. Στην αιγυπτιακή του 1834 αναφέρεται ως Kudhumalia (Pashley, Travels in Crete, II, 321) μαζί με τα χωριά Αγ. Γεώργιος, Πλαθιανώ και Αβρακόντε, με 100 χριστιανικές οικογένειες, όλα μαζί.
Το 1881 αναφέρεται στον δήμο Ψυχρού με 131 κατοίκους, το 1900 στον ίδιο δήμο με 143, στην απογραφή του 1920 είναι έδρα ομώνυμου αγροτικού δήμου με 87 κατοίκους , το 1928 άνηκε στην κοινότητα Αγ. Γεωργίου, με 148 κατοίκους , από το 1940 (μέχρι και σήμερα) ανήκει στην κοινότητα του Αβρακόντε με 192 κατοίκους , το 1951 είχε 174, το 1961 είχε 153, το 1971 είχε 74, το 1981 είχε 85, το 1991 είχε 84 και το 2001 μαζί με το χωριό του Αβρακόντε είχαν 227 μόνιμους κάτοικους.