* Οι συμμετοχές και τα γκολ στις προηγούμενες ομάδες υπολογίζονται μόνο για τα εγχώρια πρωταθλήματα και έχουν ανανεωθεί έως 31 Ιουλίου 2020.
† Συμμετοχές (Γκολ).
Ο Μαλεζάς ξεκίνησε την ποδοσφαιρική του καριέρα από την Α.Ε. Ποντίων Κατερίνης. Το 2003 πήρε μεταγραφή στον ΠΑΟΚ, ενώ κατά την περίοδο 2004-05 δόθηκε δανεικός στον Ηρόδοτο,[1] για να επιστρέψει την επόμενη χρονιά και πάλι στον "δικέφαλο του Βορρά".
Το καλοκαίρι του 2012, αποχώρησε από τον ΠΑΟΚ έπειτα από εννέα χρόνια παρουσίας, κατά τα οποία πραγματοποίησε 129 συμμετοχές πρωταθλήματος, για να συνεχίσει την καριέρα του στη Γερμανία και τη Φορτούνα Ντύσσελντορφ,[2] όπου στα δύο χρόνια παραμονής του είχε 33 συμμετοχές πρωταθλήματος, 21 στην Μπουντεσλίγκα (2012-13) και 12 στη δεύτερη κατηγορία (2013-14).
Τον Ιούλιο του 2014 επέστρεψε στο ελληνικό πρωτάθλημα υπογράφοντας συμβόλαιο διετούς συνεργασίας με τον Παναιτωλικό,[3] όμως την επόμενη χρονιά κι έπειτα από τρία χρόνια απουσίας επέστρεψε στον ΠΑΟΚ.[4] Τη δεύτερη χρονιά μετά την επιστροφή του στην ομάδα της Θεσσαλονίκης (2016-17), κατέκτησε το Κύπελλο Ελλάδος, που ήταν και ο πρώτος τίτλος στην καριέρα του. Στον τελικό ο ΠΑΟΚ επικράτησε της ΑΕΚ με 2-1, με τον ίδιο να αγωνίζεται ως αλλαγή.
Την επόμενη χρονιά με την ομάδα της Θεσσαλονίκης, αποτέλεσε έναν από τους τρεις αρχηγούς, ενώ ήταν μία αξιόπιστη λύση για την ομάδα, προερχόμενος κυρίως από τον πάγκο. Επίσης, στο φινάλε της σεζόν στέφθηκε ξανά Κυπελλούχος Ελλάδος για το 2017-2018, με τον ΠΑΟΚ να αντιμετωπίζει και να κερδίζει ξανά την ΑΕΚ με σκορ 2-0 αυτήν την φορά. Ο ίδιος αγωνίστηκε ως αλλαγή. Μπήκε στο 82' στην θέση του αρχηγού Αντελίνο Βιεϊρίνια, ενώ με την είσοδό του στον αγώνα, πήρε αυτός το περιβραχιόνιο του αρχηγού.
Ανανέωσε τη συνεργασία του με τον ΠΑΟΚ για έναν ακόμη χρόνο και τη σεζόν 2018-2019 κατέκτησε το νταμπλ (πρωτάθλημα και κύπελλο) με την ομάδα, αν και αγωνίστηκε μόλις σε τρία παιχνίδια για το κύπελλο Ελλάδας και στο πρωτάθλημα έγραψε μία συμμετοχή, «τιμητική», στο ματς που έκρινε τον τίτλο (ΠΑΟΚ - Λεβαδειακός 5-0). Με την λήξη της συνεργασίας του με την ομάδα του ΠΑΟΚ,[5] ήρθε σε συμφωνία με την ομάδα της Ξάνθης.[6][7] Με την λήξη της σεζόν 2019-2020 ανακοίνωσε την αποχώρησή του από την ενεργό δράση.[8]
Λίγους μήνες μετά επανήλθε στον ΠΑΟΚ ως προπονητής της ομάδας νέων (Κ-19),[9] όπου και κατέκτησε το πρωτάθλημα της αντίστοιχης κατηγορίας. Από την σεζόν 2023-2024 είναι προπονητής της ομάδας του Μακεδονικού.[10]
