Ο Πανθεσσαλονίκειος Αθλητικός Ομιλος Κωνσταντινουπολιτών ιδρύθηκε από Έλληνες της Κωνσταντινούπολης το 1926 και δύο χρόνια αργότερα δημιουργήθηκε το τμήμα μπάσκετ του ΠΑΟΚ. Η καλαθόσφαιρα που πραγματοποίησε τα πρώτα της βήματα στην Ελλάδα από τη Θεσσαλονίκη και το ανοικτό γήπεδο της ΧΑΝΘ, βρήκε πολύ γρήγορα πεδίο δράσης και στον ΠΑΟΚ, όταν ο Αλέκος Αλεξιάδης, ένα νεαρό μέλος του Διοικητικού Συμβουλίου του ΠΑΟΚ, αποφάσισε να προχωρήσει στην ίδρυση του τμήματος.
Ο πρώτος τίτλος του ΠΑΟΚ ήρθε το 1959 με την κατάκτηση του πρωταθλήματος που έδωσε την ευκαιρία στην ομάδα να αγωνιστεί και στο Κύπελλο Πρωταθλητριών Ευρώπης την επόμενη σεζόν. Προπονητής της ομάδας ήταν ο Ηρακλής Κλάγκας που ταυτόχρονα ήταν και παίκτης της ομάδας. Αρχικά ανακηρύχθηκε Πρωταθλητής Θεσσαλονίκης και στη συνέχεια συμμετείχε στο πανελλήνιο πρωτάθλημα μαζί με τους Σπόρτινγκ, Ολυμπιακό, ΑΕΚ, Εθνικός, Άρη και Ηρακλή. Το πρωτάθλημα διεξαγόταν στο ανοικτό γήπεδο της ΧΑΝΘ και ο ΠΑΟΚ κέρδισε στην 1η αγωνιστική τον Σπόρτινγκ (75-58), στην 2η τον Άρη (60-57), στην 3η ηττήθηκε από την ΑΕΚ με 67-69, στην 4η κέρδισε τον Εθνικό με 65-61 και στην 5η κέρδισε με 53-52 τον Ολυμπιακό και βρέθηκε αγκαλιά με τον τίτλο. Στην 6η και τελευταία αγωνιστική ο αδιάφορος Ηρακλής κέρδισε τον ΠΑΟΚ με 60-57 και ο τίτλος κρίθηκε στα μπαράζ. ΠΑΟΚ και Άρης κερδίζουν τον Σπόρτινγκ με 59-56 και 78-77 αντίστοιχα και πηγαίνουν οι δυο τους στον τελικό. Εκεί ο Γιώργος Οικονόμου με 25 πόντους οδήγησε τον ΠΑΟΚ στον τίτλο νικώντας τον Άρη με σκορ 61-58.
Ο δεύτερος τίτλος του ΠΑΟΚ ήταν το Κύπελλο το 1984, όπου νίκησε τον μεγάλο του αντίπαλο τον Άρη στο κατάμεστο Αλεξάνδρειο με 74-70 με καλύτερο του παίκτη τον Σταυρόπουλο που πέτυχε 26 πόντους. Ο τελικός αυτός έμεινε στην ιστορία ως «ο τελικός των ξυρισμένων κεφαλιών». Ήταν μία κίνηση ενότητας και επιθυμίας από τους παίκτες του ΠΑΟΚ που παραμονές του αγώνα έκοψαν πολύ κοντά τα μαλλιά τους.
Ο τρίτος τίτλος του Δικεφάλου ήταν ξεχωριστός μιας και ήταν ευρωπαϊκός. Στις 26 Μαρτίου του 1991 στο «Πατινουάρ ντε Βερνέ» ο ΠΑΟΚ κερδίζει με 76-72 τη Σαραγόσα στην Γενεύη και κατακτά το Κύπελλο Κυπελλούχων. Στην Ελβετική πόλη εκστράτευσαν περισσότεροι από 5.000 φίλοι του Δικεφάλου και έκαναν την Ευρώπη να παραμιλά. Προπονητής εκείνης της ομάδας ήταν ο Ντράγκαν Σάκοτα. Καλύτερος παίκτης του τελικού ο σημερινός πρόεδρος της ΚΑΕ ΠΑΟΚ, Μπάνε Πρέλεβιτς που πέτυχε 31 πόντους. Αυτός ο αγώνας έχει μείνει στην ιστορία για την ψυχή, την θέληση για τη νίκη αλλά και τη δύναμη που επέδειξαν σε όλη την διάρκεια του αγώνα οι παίκτες του Δικεφάλου.
Το 1992 ο ΠΑΟΚ κατακτά το πρωτάθλημα Ελλάδος (δεύτερο στην ιστορία του) και αυτό γίνεται ο 4ος τίτλος της ομάδας. Στα πλέι οφ κερδίζει δύο φορές τον Άρη και την ΑΕΚ και στους τελικούς κερδίζει τον Ολυμπιακό στο Αλεξάνδρειο με 87-67 αλλά στο δεύτερο ματς χάνει με 75-78 στο ΣΕΦ. Στο τρίτο παιχνίδι στο Στάδιο Ειρήνης και Φιλίας διαλύει τον Ολυμπιακό ξανά με 97-82 και στέλνει τους οπαδούς του ΠΑΟΚ στα ουράνια. Από εκείνη την ώρα ξεκινάει το πανηγύρι στον Πύργος τον Λευκό και οι ΠΑΟΚτσήδες περιμένουν στον αεροδρόμιο την υποδοχή των πρωταθλητών.
Ο πέμπτος τίτλος του μπασκετικού Δικεφάλου ήταν και παραμένει ιστορικός. Ο λόγος φυσικά είναι ότι ο ΠΑΟΚ έγινε η πρώτη Ελληνική ομάδα που κατέκτησε και δεύτερο Ευρωπαϊκό τίτλο (το 1994). Έχοντας παίξει καταπληκτικό μπάσκετ, κέρδισε με 75-66 στη Θεσσαλονίκη τη Στεφανέλ και με 100-91 στην Τεργέστη (16/3/1994) και με δύο νίκες κατακτά το Κύπελλο Κόρατς. Κορυφαίοι οι Μπέρι (23 πόντους) και Πρέλεβιτς (30 πόντους) αντίστοιχα.
Το έκτο τρόπαιο του ΠΑΟΚ έρχεται την αμέσως επόμενη χρονιά (1995), όταν και κατέκτησε το Κύπελλο Ελλάδας στο πρώτο φάιναλ φορ που διεξήχθη στη Λαμία. Ο ΠΑΟΚ έχοντας κερδίσει με 80-63 στον ημιτελικό τον Άρη, διαλύει στον τελικό τον Πανιώνιο με 72-53 με τον Μπάνε Πρέλεβιτς να κάνει πάρτι και στα δύο ματς (29 πόντους στον ημιτελικό, 27 πόντους στον τελικό).
Το 1999, ο ΠΑΟΚ θα κατακτήσει τον τελευταίο του τίτλο, το Κύπελλο Ελλάδος, πραγματοποιώντας εξαιρετικές εμφανίσεις. Κέρδισε με διαφορά ρεκόρ (83-50) τον Αρη στον ημιτελικό και εύκολα την ΑΕΚ στον τελικό (71-54) και ο αρχηγός εκείνης της ομάδας Γιώργος Μπαλογιάννης σηκώνει το Κύπελλο μέσα στο ΣΕΦ, που έχει κατακλυστεί από χιλιάδες φιλάθλους του ΠΑΟΚ. Προπονητής του Δικεφάλου ο Κώστας Φλεβαράκης και καλύτεροι παίκτες οι Μπαλογιάννης και Κινγκ.
Με 5 τίτλους σε μια δεκαετία, η δεκαετία του 1990 μπορεί να χαρακτηριστεί η καλύτερη όλων των εποχών για τον μπασκετικό ΠΑΟΚ.
Τη μεγαλύτερη νίκη του ο ΠΑΟΚ την πέτυχε στο Κύπελλο Κυπελλούχων όταν κέρδισε την ΑΕ Λεμεσού με 45-116 (διαφορά 71 πόντων) και στο Παλέ 120-51 (διαφορά 69 πόντων).