Το 45ο Δημοτικό Σχολείο λειτούργησε για πρώτη φορά το σχολικό έτος 1987-1988 προκειμένου να καλύψει την ολοένα και αυξανόμενη πληθυσμιακά περιοχή των Τριών Βαγιών και Αγ. Ιωάννη Χωστού. Είχε ιδρυθεί ένα χρόνο νωρίτερα με το ΦΕΚ τ.Α΄146/30-9-1986. Αρχικά στεγαζόταν μαζί με το 33ο Δημοτικό Σχολείο και το 9ο Γυμνάσιο στην περιοχή των Καμινίων με αποτέλεσμα να λειτουργεί σε πρωινή και απογευματινή βάρδια. Αργότερα ιδρύθηκε ο Σύλλογος Γονέων και Κηδεμόνων με πρόεδρο τον κ. Χαράλαμπο Νησωτάκη και ξεκίνησε η διαδικασία της εύρεσης χώρου προκειμένου να μεταφερθεί σε δικό του κτίριο. Ενώ οι εργασίες του χτισίματος προχωρούσαν το σχολείο είχε μεταφερθεί στο ΕΕΕΕΚ Ηρακλείου στον Αγ. Ιωάννη Χωστό. Τελικά το νέο κτίριο εγκαινιάστηκε το 2009. Πρόκειται για ένα σύγχρονο διδακτήριο το οποίο καλύπτει τις σύγχρονες ανάγκες ενός σχολείου διαθέτοντας αίθουσα υπολογιστών, μουσικής, πολλαπλών χρήσεων, εικαστικών και τμήμα ένταξης. Σήμερα αν και 12/θέσιο λειτουργεί με 19 τμήματα και 420 μαθητές καλύπτοντας πληθυσμιακά τις περιοχές Φοινικιάς, Μαλάδων, Κάμπου Αγ. Σύλλα και Κορακοβουνίου καθιστώντας το έτσι ένα από τα μεγαλύτερα σχολεία της Κρήτης. Ο πρώτος διευθυντής του Σχολείου ήταν ο κ. Μαυρομανωλάκης Αλέξανδρος, ο οποίος συνταξιοδοτήθηκε το 2007 ενώ από τότε ως τις μέρες μας διευθυντής του σχολείου είναι ο κ. Ντρουμπογιάννης Χρήστος.

Tα παιδιά σε ώρα διαλείμματος