1993 Η χαμένη ευκαιρία της Αθήνας
Από την περίοδο 1992-93 επιτράπηκε η συμμετοχή και δεύτερου ξένου στο Ελληνικό πρωτάθλημα και δίπλα στον Μπάρλοου, ήρθε ο πρωταθλητής του ΝΒΑ με τους Σικάγο Μπουλς Κλιφ Λέβινγκστον. Εχοντας πλέον και τον Κόρφα στις ευρωπαϊκές του υποχρεώσεις και το Μπουντούρη με πολλές παραστάσεις στα 22 του, ο ΠΑΟΚ παίζει καταπληκτικό μπάσκετ, αποσπά τον θαυμασμό όλης της Ευρώπης, παραδίδει μαθήματα όπου κι αν παίζει, φτάνει με πανηγυρικό τρόπο στο φάιναλ φορ της Αθήνας κι εκεί πέφτει πάνω στη Μπενετόν Τρεβίζο, που αποδεικνύεται αξεπέραστο εμπόδιο. Νέα απογοήτευση, μεγαλύτερη από κάθε φορά. Ο Νίκος Βεζυρτζής αφήνει την ομάδα στον Απόστολο Οικονομίδη, ο Παναγιώτης Φασούλας αποχωρεί και το ίδιο συμβαίνει και με το δίδυμο των ξένων.
1994 Ο δεύτερος ευρωπαϊκός τίτλος
Με δίδυμο ξένων πλέον Μπέρι και Σάβιτς, με το Σούλη Μαρκόπουλο να παίρνει τη θέση του Ιβκοβιτς από τα μισά της περιόδου και αρκετά νέα πρόσωπα ακόμη (Γαλακτερός, Ρεντζιάς) ο ΠΑΟΚ θα γίνει η πρώτη Ελληνική ομάδα που θα κατακτήσει και δεύτερο Ευρωπαϊκό τίτλο. Η πορεία του ΠΑΟΚ για την κατάκτηση του τίτλου ήταν θριαμβευτική. Σάρωσε κάθε αντίπαλο που βρήκε μπροστά του, με δύο νίκες στα ημιτελικά, ξεπέρασε και τα εμπόδιο του Πανιωνίου στον πρώτο ελληνικό εμφύλιο και όταν συνάντησε την Στεφανέλ σε διπλούς τελικούς, απέδειξε με τον πλέον χαρακτηριστικό τρόπο ποια είναι η καλύτερη ομάδα. Νίκη αρχικά (85-76) στο Αλεξάνδρειο και δεύτερη νίκη, με το απόλυτο μπάσκετ και σκορ 100-91 στο δεύτερο παιχνίδι που έγινε στην Τεργέστη.
Η χρονιά θα μπορούσε να είχε ολοκληρωθεί με τον ιδανικό τρόπο, εάν δεν συνέβαιναν διάφορα και δεν έχανε ο ΠΑΟΚ το πρωτάθλημα στις λεπτομέρειες και για καθαρά εξωαγωνιστικούς λόγους. Με κεκτημένη ταχύτητα από την κατάκτηση του Κυπέλλου Κόρατς, ο ΠΑΟΚ έφτασε στους τελικούς των πλέι οφ, διεκδίκησε ως το τέλος και στο πέμπτο παιχνίδι τον τίτλο, αλλά τον έχασε από μία λανθασμένη υπόδειξη στο πιο κρίσιμο σημείο του αγώνα.
1995 Περίπατος στη Λαμία
O ΠΑΟΚ ήταν συνεπής στο ραντεβού του με την ιστορία, έναν ακόμη τελικό, αλλά και τον επόμενο τίτλο που μπήκε στην τροπαιοθήκη του συλλόγου. Ξεκινώντας με προπονητή τον Ντράγκαν Σάκοτα και στην πορεία με τον Σάκη Λάιο στη θέση του, ο ΠΑΟΚ έφτασε ως το πρώτο φάιναλ φορ του Κυπέλλου Ελλάδας, το οποίο διεξήχθη στη Λαμία και το οποίο κατέκτησε με χαρακτηριστική ευκολία. Ξεπερνώντας με άνεση το εμπόδιο του Άρη στον ημιτελικό (80-63), ο ΠΑΟΚ ήταν απόλυτος κυρίαρχος και στον τελικό απέναντι στον Πανιώνιο. Νίκη με 72-53, με απόλυτο πρωταγωνιστή και πολυτιμότερο παίκτη τον αρχηγό του Μπάνε Πρέλεβιτς.
Αγωνιζόμενος στην Ευρωλίγκα εκείνης της σεζόν, ο ΠΑΟΚ κατάφερε να περάσει στη δεύτερη φάση, χωρίς όμως να έχει τη δυνατότητα μίας σπουδαίας διάκρισης, ενώ και στο πρωτάθλημα η πορεία του ήταν μέτρια και ολοκληρώθηκε με άσχημο τρόπο. Στη διάρκεια των πλέι οφ ο ΠΑΟΚ άλλαξε και πάλι προπονητή και με τον Βαγγέλη Αλεξανδρή στον πάγκο προσπάθησε, αλλά δεν κατάφερε να γυρίσει την κατάσταση και έμεινε στην 4η θέση, πίσω από τον 3ο Ηρακλή και εκτός Ευρωλίγκα για την επόμενη σεζόν.
1996 Ο τελευταίος ευρωπαϊκός τελικός
Η σεζόν 1995-96 ήταν από τις πιο περίεργες στην ιστορία του ΠΑΟΚ. Η χρονιά ξεκίνησε και τελείωσε με αλλαγή προπονητή. Συνολικά τέσσερις προπονητές οδήγησαν την ομάδα, ξεκινώντας από τον Βαγγέλη Αλεξανδρή, συνεχίζοντας με τον Ευθύμη Κιουμουρτζόγλου, τον Δημήτρη Ιτούδη που κοουτσάρισε την ομάδα για ένα ματς, προτού αναλάβει ο Ζέλικο Λούκαϊτς. Η χρονιά πάντως τελείωσε με τον Δημήτρη Ιτούδη στον πάγκο του ΠΑΟΚ στα πλέι οφ. Και πάλι ο ΠΑΟΚ έμεινε στην 4η θέση, χάνοντας τη σειρά των μικρών τελικών από τον Πανιώνιο, στην τελευταία χρονιά του Μπάνε Πρέλεβιτς με την ομάδα.
Το 1996 ήταν και ευρωπαϊκή χρονιά όμως, καθώς ο ΠΑΟΚ συμμετείχε για τελευταία φορά σε έναν τελικό. Με θριαμβευτική πορεία ο ΠΑΟΚ πέρασε σαν σίφουνας το εμπόδιο της Ζαλγκίρις Κάουνας στον ημιτελικό και διεκδίκησε το τρόπαιο και τον τρίτο του ευρωπαϊκό τίτλο ως το τέλος. Ηττήθηκε όμως (88-81) από την γηπεδούχο Ταουγκρές στη Βιτόρια της Ισπανίας κι αυτό που του έμεινε ήταν η αναγνώριση της προσπάθειάς του ακόμη και από τους φιλάθλους της γηπεδούχου ομάδας.
Ο Ιούνιος του 1996, είχε και μία ακόμη ιδιαίτερη στιγμή για τον ΠΑΟΚ. Η επιλογή δύο παικτών του ΠΑΟΚ στον πρώτο γύρο του ντραφτ του ΝΒΑ, αποτέλεσε την καλύτερη επιβεβαίωση ότι επρόκειτο για μία ομάδα με μέλλον. Ο Πρέντραγκ Στογιάκοβιτς επιλέχθηκε στο 14 από τους Σακραμέντο Κινγκς κι αυτό ήταν ουσιαστικά το πρώτο βήμα για να πραγματοποιήσει μία σπουδαία καριέρα στο καλύτερο πρωτάθλημα του κόσμου, ενώ ο Ευθύμης Ρεντζιάς επιλέχθηκε στο 23 από τους Ντένβερ Νάγκετς.
1997 Στον αστερισμό του Σκοτ Σκάιλς
Η σεζόν 1996-97 ξεκίνησε με τον ΠΑΟΚ να αγωνίζεται για πρώτη φορά χωρίς τον Μπάνε Πρέλεβιτς που είχε αποχωρήσει για την Κίντερ Μπολόνια, με τον Γάλλο Μισέλ Γκομέζ στη θέση του προπονητή κι έναν σπουδαίο αμερικανό πλέι μέικερ, τον Σκοτ Σκάιλς να είναι το νέο αστέρι της ομάδας. Σε καθαρά ατομικό επίπεδο η χρονιά στιγματίστηκε από τον σοβαρό τραυματισμό του Στογιάκοβιτς (διπλό κάταγμα κνήμης-περόνης, που τον κράτησε για αρκετούς μήνες εκτός αγώνων) και την αιφνιδιαστική, αλλά και άκρως επιτυχημένη απόφαση του τότε προέδρου Απόστολου Αλεξόπουλου, να αναθέσει στον Σκάιλς την τεχνική ηγεσία της ομάδας.
Αν και ξεκίνησε από την 6η θέση της κανονικής περιόδου, ο ΠΑΟΚ πραγματοποίησε εκπληκτικές εμφανίσεις και ξεπέρασε αρχικά το εμπόδιο του Παναθηναϊκού (με 2-1 νίκες και παρά το γεγονός ότι είχε μειονέκτημα έδρας). Ο ΠΑΟΚ δεν κατάφερε να κοντράρει την ΑΕΚ στους ημιτελικούς των πλέι οφ και διεκδίκησε την 3η θέση και την συμμετοχή του στην Ευρωλίγκα της επόμενης σεζόν, στους αγώνες με το Περιστέρι. Αν και μπήκε στη σειρά με μειονέκτημα έδρας, ο ΠΑΟΚ κυριάρχησε και με 3-1 νίκες πέτυχε τον στόχο του, με τρόπο μάλιστα πολύ εμφατικό, όπως μαρτυρά και το εντυπωσιακό 78-47 του τελευταίου αγώνα στο Αλεξάνδρειο.
1998 Το τρίποντο-ζωγραφιά του Στογιάκοβιτς
Ο ΠΑΟΚ ξεκινά τη σεζόν με τον Ισραηλινό Σβι Σερφ σε ρόλο προπονητή. Μετά από αρκετή ταλαιπωρία και τραυματισμούς, ο Πρέντραγκ Στογιάκοβιτς επιστρέφει στο ξεκίνημα της σεζόν 1997-98, πραγματοποιεί την καλύτερή του χρονιά με τον ΠΑΟΚ, την μοναδική χωρίς απουσίες και προβλήματα, αλλά και αυτήν που έμελε να είναι η τελευταία του με την ομάδα. Ήταν τέτοιο το ταλέντο του, που δεν μπορούσε να μείνει περιορισμένος στα στενά όρια του ελληνικού και ευρωπαϊκού μπάσκετ. Το ΝΒΑ ήταν ο μοναδικός του προορισμός κι αυτό αποδείχθηκε στην πορεία…
Ο Στογιάκοβιτς ήταν ο καλύτερος παίκτης του ΠΑΟΚ σε όλη τη διάρκεια της σεζόν και έβαλε την υπογραφή του με τον πιο χαρακτηριστικό τρόπο στην επική πρόκριση της ομάδας στους τελικούς των πλέι οφ. Με τρίποντο του Στογιάκοβιτς στη λήξη του τρίτου και καθοριστικού ημιτελικού, ο ΠΑΟΚ έριξε στο καναβάτσο τον Ολυμπιακό, τον γκρέμισε από την κορυφή του ελληνικού μπάσκετ και διεκδίκησε ως το τέλος τον τίτλο, χάνοντας στο 5ο παιχνίδι (και με 2-3 νίκες) από τον Παναθηναϊκό.
1999 Το τελευταίο Κύπελλο
Ο ΠΑΟΚ ολοκληρώνει μία σπουδαία πορεία η οποία κράτησε μία δεκαετία, με συνεχόμενες συμμετοχές σε τελικούς και συνολικά πέντε τίτλους που ήρθαν σε αυτό το διάστημα. Ο τελευταίος εξ αυτών ήταν το Κύπελλο Ελλάδας το 1999, που αποτελεί και την τελευταία μεγάλη επιτυχία της ομάδας μέχρι και σήμερα. Ξεκινώντας τη σεζόν με τον Σβι Σερφ στον πάγκο, ο ΠΑΟΚ πετυχαίνει μία σπουδαία εκτός έδρας νίκη (61-52) επί του Ολυμπιακού στο ΣΕΦ και εξασφαλίζει την συμμετοχή του στο φάιναλ φορ του Κυπέλλου.
Μέχρι να έρθει η ώρα να διεκδικήσει τον τίτλο, ο ΠΑΟΚ είχε ήδη αλλάξει προπονητή και πήγε στο φάιναλ φορ που διεξήχθη στο ΣΕΦ με τον Κώστα Φλεβαράκη στον πάγκο. Με τον Γουόλτερ Μπέρι να αναδεικνύεται πολυτιμότερος παίκτης των αγώνων και τον αρχηγό Γιώργο Μπαλογιάννη να πραγματοποιεί καταπληκτικές εμφανίσεις, ο ΠΑΟΚ έφτασε στην κατάκτηση του Κυπέλλου με δύο εμφατικές νίκες. Συνέτριψε τον Άρη με διαφορά 33 πόντων (83-50) στον ημιτελικό και νίκησε με χαρακτηριστική άνεση (71-54) και την ΑΕΚ, κατακτώντας το τρόπαιο. Οι κακές καιρικές συνθήκες δεν αποτέλεσαν αξεπέραστο εμπόδιο ούτε για τους χιλιάδες φιλάθλους του ΠΑΟΚ που ταξίδεψαν ως την Αθήνα και κατέκλυσαν το ΣΕΦ, ούτε όμως και για την αποστολή του ΠΑΟΚ που επέστρεψε στη Θεσσαλονίκη με τρένο και γνώρισε αποθεωτική υποδοχή.
2000 Το νέο σπίτι του ΠΑΟΚ
Με τον Μπάνε Πρέλεβιτς να επιστρέφει στη Θεσσαλονίκη για να κλείσει την καριέρα του στον ΠΑΟΚ, η σεζόν 1999-00 έμοιαζε ιστορική από το ξεκίνημά της. Και ήταν, παρά το γεγονός ότι σε αγωνιστικό επίπεδο δεν έφερε κάποια μεγάλη επιτυχία. Ωστόσο, ο ΠΑΟΚ διεκδίκησε ως το τέλος την συμμετοχή στο Φάιναλ Φορ της Ευρωλίγκα, το οποίο πραγματοποιήθηκε στο νέο του γήπεδο, όπως ακριβώς συνέβη και με το Φάιναλ Φορ του Κυπέλλου. Δυστυχώς ο ΠΑΟΚ δεν κατάφερε να προκριθεί σε καμία από τις δύο διοργανώσεις που έγιναν στο γήπεδό του τον Απρίλιο του 2000. Ο ΠΑΟΚ όμως, είχε το δικό του γήπεδο, στο οποίο πραγματοποίησε την πρώτη του προπόνηση στις 30 Μαρτίου 2000.
Η νέα χιλιετία βρήκε τον ΠΑΟΚ και πάλι στον τελικό των πλέι οφ. Ξεπέρασε το εμπόδιο του Ολυμπιακού στα ημιτελικά, με νίκη στο ΣΕΦ με την υπογραφή του Μπαλογιάννη και το εντυπωσιακό 86-66 στο τελευταίο παιχνίδι της ομάδας στο Αλεξάνδρειο. Στις 17 Μαΐου του 2000, ο ΠΑΟΚ αγωνίστηκε για πρώτη φορά στο νέο του γήπεδο. Στο «κατάμεστο» PAOK Sports Arena υποδέχθηκε τον Παναθηναϊκό στον δεύτερο τελικό των πλέι οφ και παρά την μεγάλη του προσπάθεια δεν κατάφερε να φτάσει στον τίτλο. Είχε όμως το δικό του γήπεδο κι αυτό από μόνο του έμοιαζε με την κατάκτηση του πρωταθλήματος.