Το Επαγγελματικό Λύκειο Ηράκλειας ιδρύθηκε 
το 1997. Αρχικά, ως Τ.Ε.Ε. Ηράκλειας, φιλοξενήθηκε και λειτούργησε στο Δημοτικό Σχολείο Κεσάνης, την σχολική χρονιά 1998-1999. Το έτος 2000 εγκαταστάθηκε στον ίδιο προαύλιο χώρο με το Γυμνάσιο και το Γενικό Λύκειο Ηράκλειας. Η πρόβλεψη ήταν να στεγαστεί σε λυόμενες αίθουσες τύπου container – μέχρι να οικοδομηθεί κτίριο που θα καλύπτει τις εκπαιδευτικές ανάγκες του σχολείου – σε τμήμα προαύλιου χώρου που παραχωρήθηκε από το Γυμνάσιο ενώ τα γραφεία της διοίκησης, των εκπαιδευτικών καθώς και τα εργαστήρια πληροφορικής σε άλλο τμήμα του ίδιου προαύλιου χώρου. Οι πρώτοι τομείς που λειτούργησαν στο σχολείο ήταν η Οικονομία-Διοίκηση (Ειδικότητα Υπαλλήλων Οικονομικών Υπηρεσιών) και η Πληροφορική (Ειδικότητα Υποστήριξης Συστημάτων-Εφαρμογών και Δικτύων Η/Υ) ακολουθούμενες δύο χρόνια αργότερα από τον τομέα της Υγείας-Πρόνοιας (Ειδικότητα Βοηθών Νοσηλευτών). Από το 2009 η Γ τάξη του τομέα Υγείας-Πρόνοιας χωρίζεται στην ειδικότητα των Βοηθών Νοσηλευτών και στην ειδικότητα των Βοηθών Βρεφονηπιοκόμων.