Το τμήμα πετοσφαίρισης ανδρών του ΠΑΟΚ ιδρύθηκε το 1933. Επανιδρύθηκε το 1948, μετά την Κατοχή για μικρό διάστημα, ενώ επανιδρύθηκε εκ νέου το 1961.
Ο ΠΑΟΚ μετείχε σε 34 πρωταθλήματα Α' και Α1 εθνικής κατηγορίας από την καθιέρωσή της, την περίοδο 1968–69. Η καλύτερη θέση που είχε καταλάβει στην τελική κατάταξη ως το 2015 ήταν η 3η, το 2013.
Στο Κύπελλο Ελλάδας η μεγαλύτερη διάκρισή του ήταν το 1983, όταν έφτασε μέχρι τον τελικό, όπου όμως ηττήθηκε με 3–1 σετ από τον πρωταθλητή τη χρονιά εκείνη, Ολυμπιακό.
Η επανάσταση του ΠΑΟΚ στο βόλεϊ, ήρθε την περσινή σεζόν. Με τον Γιώργο Ανδρέου να τινάζει το μπάτζετ στα ύψη, φέρνοντας στη Θεσσαλονίκη ονόματα παγκόσμιου βεληνεκούς, όπως οι Γκόμεζ, Χιμένεζ, Σαφράνοβιτς, αλλά και έναν παίκτη που έχει σαρώσει τα πάντα στην καριέρα του από τίτλους, ο λόγος για τον Βασίλη Κουρνέτα και έναν έμπειρο προπονητή που έχει φάει με το κουτάλι τα ελληνικά γήπεδα, τον Γιάννη Καλμαζίδη, ο Δικέφαλος κατάφερε να πετύχει ένα άθλο!
Η αρχή έγινε με την κατάκτηση του Κυπέλλου Ελλάδας στη Σύρο, όμως η συνέχεια ήταν ονειρική για το σύλλογο, καθώς διέλυσε τον Ολυμπιακό και στη σειρά των τελικών του πρωταθλήματος της Volley League, φτάνοντας στην κατάκτηση του τίτλου, μπροστά σε 10.000 φίλους του που βρέθηκαν και έζησαν μαγικές στιγμές στο PAOK SPORTS ARENA.
ΧΑΝΤΜΠΟΛ
Το ανδρικό τμήμα Handball ιδρύθηκε το 1999 μετά από συγχώνευση με τον Τρίτωνα. Πρωτεργάτης της ίδρυσης ήταν ο ακάματος εργάτης του αθλήματος Θανάσης Σιούλης. Δέκα χρόνια αργότερα ο ΠΑΟΚ έφτασε στην κορυφή του αθλήματος.
Το Μάρτιο του 2015 το τμήμα Handball έγινε το πρώτο στην ιστορία του συλλόγου που κατέκτησε τρόπαιο μέσα στο PAOK Sports Arena, νικώντας την ΑΕΚ στον τελικό του Κυπέλλου Ελλάδος, που στιγματίστηκε από τα επεισόδια των οπαδών των δυο ομάδων.
Συνολικά, ο ΠΑΟΚ έχει κατακτήσει τρία πρωταθλήματα Ελλάδος (2009, 2010, 2015) και δύο κύπελλα Ελλάδος (2012, 2015)
Το γυναικείο τμήμα Handball ιδρύθηκε το 2007, με έφορο από την πρώτη μέρα έως και σήμερα τον Δημήτρη Χασεκίδη. Την πρώτη χρονιά, με προπονητή τον Νέναντ Πίβατς, η ομάδα ανέβηκε στην Α2. Έκτοτε ξεκίνησε η κοινή πορεία με την προπονήτρια Γρηγορία Γκόλια, που συνεχίζεται μέχρι σήμερα.
Η παρουσία του τμήματος στο άθλημα θεωρείται άκρως επιτυχημένη, καθώς ήδη μετρά τρεις τίτλους, το πρωτάθλημα Ελλάδος του 2013 και τα δύο Κύπελλα Ελλάδος που κατέκτησε το 2014 και το 2016.
Κολύμβηση
Το Κολυμβητικό Τμήμα ιδρύθηκε το 1931 και είναι ένα από τα δυναμικότερα, παλαιότερα και δημοφιλέστερα του συλλόγου.
Πρωταθλητές Ελλάδος με διεθνείς διακρίσεις ήταν οι εξής αθλητές: Κλέπκου Κατερίνα (Ολυμπιακοί 1996), Μαχαίρα Τόνια (Ολυμπιακοί 2000), Σαρακατσάνη Κάτια (Ολυμπιακοί 2000), Μποχώρη Αθηνά (Ολυμπιακοί 2000), Τσιτσέ Βίκη (Παγκόσμιοι 2002), Παρασκευόπουλος Νίκος, Κουγιουμτζόγλου Σάββας, Γιαννούλης Γιάννης (Ολυμπιακοί 2008), Φωκαίδης Αντώνης(Παγκόσμιοι 2009, 2011), Λιούπης Ματέο.
ΣΗΜΑΝΤΙΚΟΤΕΡΕΣ ΕΠΙΤΥΧΙΕΣ
- ΠΡΩΤΑΘΛΗΤΕΣ ΕΛΛΑΔΟΣ ΟΠΕΝ ΑΝΔΡΩΝ-ΓΥΝΑΙΚΩΝ 1987.
- ΠΡΩΤΑΘΛΗΤΕΣ ΕΛΛΑΔΟΣ ΕΦΗΒΩΝ-ΝΕΑΝΙΔΩΝ 1990.
- ΠΡΩΤΑΘΛΗΤΕΣ ΕΛΛΑΔΟΣ ΓΥΝΑΙΚΩΝ ΟΠΕΝ 1999 ΚΑΙ 2000.
- ΠΡΩΤΑΘΛΗΤΕΣ ΕΛΛΑΔΟΣ ΝΕΑΝΙΔΩΝ 2005.
- 2005 και 2006 2οι στην ΟΠΕΝ ΑΝΔΡΩΝ και 3οι στη Γενική Βαθμολογία ΟΠΕΝ ΑΝΔΡΩΝ-ΓΥΝΑΙΚΩΝ.
- 2007 Πρωταθλητές ΕΦΗΒΩΝ και 2οι στην ΟΠΕΝ ΑΝΔΡΩΝ-ΓΥΝΑΙΚΩΝ.
- ΠΡΩΤΑΘΛΗΤΕΣ ΕΛΛΑΔΟΣ ΕΦΗΒΩΝ – ΝΕΑΝΙΔΩΝ 2008 και 2009.
- 2008 2οι στους ΑΝΔΡΕΣ, 3οι στις ΓΥΝΑΙΚΕΣ και 2οι στη Γενική Βαθμολογία στο Πανελλήνιο Πρωτάθλημα ΑΝΔΡΩΝ-ΓΥΝΑΙΚΩΝ ΟΠΕΝ.
- H ομάδα είναι Πρωταθλήτρια Θεσσαλονίκης στις Προαγωνιστικές Κατηγορίες (10-11-12 ετών) 2008-2012 με μεγάλη διαφορά από τις άλλες ομάδες.
Ποδηλασία
Το ποδηλατικό τμήμα του ΠΑΟΚ δημιουργήθηκε με την ίδρυση του συλλόγου, το 1926 και είναι ένα από τα παλαιότερα τμήματα στην Ελλάδα και από τα πολυπληθέστερα στη Β. Ελλάδα.
Το 2002 η ομάδα ποδηλασίας του ΠΑΟΚ κατέκτησε το πρωτάθλημα Ελλάδας στην ορεινή ποδηλασία (Μountain Bike), αφού διέθετε στο δυναμικό της τον Πρωταθλητή Μανόλη Κωτούλα, ο οποίος συμμετείχε στη Ολυμπιάδα του 2004 στην Αθήνα. Σημαντική στιγμή για την πορεία του τμήματος το 2007, αποτέλεσε η μεταγραφή σε αυτό του πολλάκις Πρωταθλητή Ελλάδος, Κυπελλούχου Κόσμου και παγκόσμιου Πρωταθλητή Γιάννη Ταμουρίδη, ο οποίος συμμετείχε στην Ολυμπιάδα του Λονδίνου το 2012.
Σκάκι
Το σκακιστικό τμήμα του ΑΣ ΠΑΟΚ αποτελεί το νεότερο σε σύσταση τμήμα, καθώς η απόφαση δημιουργίας του ελήφθη μόλις το Σεπτέμβριο του 2013.
Επικεφαλής του τμήματος είναι ο κύριος Σάββας Μάτσας, ο οποίος σε συνεργασία με τον Αστέριο Κόμσουλα που προπονεί τις ομάδες, ευελπιστεί να δημιουργήσει αθλητές ικανούς να εκπροσωπήσουν τον ΠΑΟΚ σε εγχώριες και διεθνείς διοργανώσεις.
Στίβος
Το τμήμα ιδρύθηκε το 1926 και από τότε βρίσκεται σε λειτουργία. Έχουν περάσει πολλοί μεγάλοι αθλητές και αθλήτριες από το τμήμα και έχουν γράψει ο καθένας τους την δική τους ιστορία στον Ελληνικό κλασσικό αθλητισμό.
Άρση Βαρών
Το τμήμα άρσης βαρών του ΠΑΟΚ ιδρύθηκε το 1999 από τον Ολυμπιονίκη Παύλο Σαλτσίδη. Στην τροπαιοθήκη του τμήματος βρίσκονται 1 πρωτάθλημα Ελλάδος (2006), 5 πανελλήνια πρωταθλήματα νέων ανδρών (2003, 2004, 2012, 2013, 2014), 4 πανελλήνια πρωταθλήματα εφήβων (2004, 2005, 2013, 2014) και 1 πανελλήνιο πρωτάθλημα παίδων (2012)
Πάλη
Το τμήμα πάλης του ΠΑΟΚ ιδρύθηκε το Σεπτέμβριο του 1998 από τον αείμνηστο Ολυμπιονίκη Παναγιώτη Ποικιλίδη. Για ένα μικρό χρονικό διάστημα η λειτουργία του τμήματος ανεστάλη και το φθινόπωρο του 2000 ανέλαβαν την ανασύστασή του οι προπονητές Δημήτρης Τσεκερίδης και Γιάννης Σισμανίδης.
Στο πέρασμα των χρόνων, αθλητές του τμήματος κατέκτησαν πανελλήνιες νίκες σε όλες τις ηλικιακές κατηγορίες. Τον Αύγουστο του 2014 ο αθλητής του τμήματος Δημήτρης Τσεκερίδης (γιος του προπονητή) κατέκτησε το χάλκινο μετάλλιο στο παγκόσμιο πρωτάθλημα ελληνορωμαϊκής πάλης εφήβων που διεξήχθη στο Ζάγκρεμπ.