Το τμήμα βόλεϊ του ΠΑΟΚ το 2013 συμπλήρωσε 80 χρόνια ζωής αν και ενδιάμεσα υπήρχαν δύο μεγάλα «κενά». Το τμήμα ιδρύθηκε το 1933 αλλά μετά τα γεγονότα του Β΄ παγκοσμίου πολέμου υπήρξε αναστολή λειτουργίας και επανιδρύθηκε το 1948, μετά την κατοχή και για μικρό χρονικό διάστημα όπου δεν είχε να παρουσιάσει κάτι το ιδιαίτερο εκτός από τις παρουσίες στα τοπικά πρωταθλήματα Θεσσαλονίκης. Με την καθιέρωση των μεταπολεμικών Πανελληνίων πρωταθλημάτων το τμήμα επανιδρύεται για τρίτη φορά το 1961 και από τότε λειτουργεί χωρίς παύση έχοντας σταθερή και συνεπή παρουσία. Βέβαια πέρασαν 11 χρόνια μέχρι η ομάδα να μπει σε τροχιά ανόδου στην Α΄Εθνική και αυτό συνέβη για πρώτη φορά στο πρωτάθλημα περιόδου 1970-71 αλλά δε μπόρεσε να αντέξει τον ανταγωνισμό και υποβιβάστηκε στα τοπικά με 22 ήττες σε ισάριθμους αγώνες.
Η πιο σοβαρή προσπάθεια για να παίξει η ομάδα πρωταγωνιστικό ρόλο γίνεται μερικά χρόνια αργότερα. Τη σεζόν 1978-79 η ομάδα αγωνίζεται πάλι στην Α΄Εθνική και πλασαρίζεται στην 9η θέση. Ούτε και τότε μπόρεσε να σωθεί. Έπεσε στη Β΄Εθνική αλλά επανήλθε άμεσα και από τη σεζόν 1980-81 μέχρι και το 2013 έχει συνεχόμενη παρουσία στην Α΄Εθνική (Α1 – Volleyleague).
Κορυφαία στιγμή στην πορεία του τμήματος ήταν η 3η θέση που κατέκτησε τη σεζόν 2012-13 που είναι και η καλύτερη όλων των εποχών καθώς 8 φορές είχε πάρει την 4η θέση (1986, 1999, 2000, 2004, 2005, 2006, 2007, 2011).
Επίσης, στο Κύπελλο Ελλάδος η καλύτερη παρουσία σημειώθηκε τη σεζόν 1982-83 όπου έφτασε μέχρι τον τελικό της διοργάνωσης που έγινε στο Αλεξάνδρειο. Εκεί ηττήθηκε 3-1 (16-14, 15-11, 04-15, 15-08) από τον Ολυμπιακό. Σε εκείνη την ομάδα προπονητής ήταν ο Ιεροκλής και παίκτες οι Βενετικίδης, Φλώρος, Καραβιδόπουλος, Χρησταράς, Κωνσταντινίδης, Νικηφορίδης (βασική ομάδα) και αλλαγές οι Γιαννόπουλος, Βασιλικούδης, Κασαπόπουλος, Καλατζίδης, Μπάλας.
Άλλες τέσσερις φορές έχει φτάσει μέχρι τα ημιτελικά (φάιναλ-4) του Κυπέλλου (1999, 2003, 2004, 2011) αλλά δεν πέρασε στον τελικό. Την περίοδο 2012-13 αγωνίστηκε και στο φάιναλ-4 του 2ου Λιγκ Καπ αλλά η πορεία του σταμάτησε από τον Ολυμπιακό στον ημιτελικό.
Την περίοδο 2014-15 το τμήμα βόλλευ του ΠΑΟΚ γίνεται η πρώτη ομάδα στην ιστορία του Συλλόγου που κατακτά πρωτάθλημα και κύπελλο.
Το 2015-16 κατακτά για δεύτερη συνεχόμενη χρονιά το πρωτάθλημα Ελλάδας, ενώ την περίοδο 2016-17 έρχεται το τρίτο συνεχόμενο πρωτάθλημα.
Η σεζόν 2017-18 βρίσκει τον ΠΑΟΚ στη δεύτερη θέση του πρωταθλήματος και Κυπελλούχο για δεύτερη φορά στην ιστορία του, ενώ το ίδιο συνέβη και στην αγωνιστική περίοδο 2018-19, όπου ο Δικέφαλος κατέκτησε το τρίτο κύπελλο και ήταν φιναλίστ του τελικού του πρωταθλήματος.
Γυναικείο Τμήμα
Από το 1985 η ομάδα συμμετείχε στις τοπικές κατηγορίες. Το 1991 για πρώτη φορά αγωνίστηκε στο πρωτάθλημα της Α2 καταλαμβάνοντας την 4η θέση και την 7η στην επόμενη σεζόν. Το 2001 επανιδρύονται οι ακαδημίες του τμήματος από τον Θανάση Μελιγκοτσίδη. Από τη σεζόν 2013-14 αγωνίζεται στο πρωτάθλημα της Β’ εθνικής κατηγορίας για να έρθει η σεζόν 2017-18, όπου η ομάδα αγωνίζεται στην Α2 Γυναικών και κατακτά το πρωτάθλημα. Την αγωνιστική χρονιά 2018-19 είναι μια χρονιά ορόσημο για το τμήμα, καθώς με την κατάκτηση του πρωταθλήματος της Pre League ήρθε και η άνοδος στη Volley League Γυναικών, για πρώτη φορά στη ιστορία του συλλόγου.
Στη τροπαιοθήκη της ομάδας υπάρχουν 1 πρωτάθλημα Pre League, 1 πρωτάθημα Α2, 1 πρωτάθλημα και 1κύπελλο Ε.ΠΕ.Σ.Θεσσαλονίκης.