Η σεζόν 1995-96 ήταν από τις πιο περίεργες στην ιστορία του ΠΑΟΚ. Η χρονιά ξεκίνησε και τελείωσε με αλλαγή προπονητή. Συνολικά τέσσερις προπονητές οδήγησαν την ομάδα, ξεκινώντας από τον Βαγγέλη Αλεξανδρή, συνεχίζοντας με τον Ευθύμη Κιουμουρτζόγλου, τον Δημήτρη Ιτούδη που κοουτσάρισε την ομάδα για ένα ματς, προτού αναλάβει ο Ζέλικο Λούκαϊτς. Η χρονιά πάντως τελείωσε με τον Δημήτρη Ιτούδη στον πάγκο του ΠΑΟΚ στα πλέι οφ. Και πάλι ο ΠΑΟΚ έμεινε στην 4^η θέση, χάνοντας τη σειρά των μικρών τελικών από τον Πανιώνιο, στην τελευταία χρονιά του Μπάνε Πρέλεβιτς με την ομάδα.

Το 1996 ήταν και ευρωπαϊκή χρονιά όμως, καθώς ο ΠΑΟΚ συμμετείχε για τελευταία φορά σε έναν τελικό. Με θριαμβευτική πορεία ο ΠΑΟΚ πέρασε σαν σίφουνας το εμπόδιο της Ζαλγκίρις Κάουνας στον ημιτελικό και διεκδίκησε το τρόπαιο και τον τρίτο του ευρωπαϊκό τίτλο ως το τέλος. Ηττήθηκε όμως (88-81) από την γηπεδούχο Ταουγκρές στη Βιτόρια της Ισπανίας κι αυτό που του έμεινε ήταν η αναγνώριση της προσπάθειάς του ακόμη και από τους φιλάθλους της γηπεδούχου ομάδας.

Ο Ιούνιος του 1996, είχε και μία ακόμη ιδιαίτερη στιγμή για τον ΠΑΟΚ. Η επιλογή δύο παικτών του ΠΑΟΚ στον πρώτο γύρο του ντραφτ του ΝΒΑ, αποτέλεσε την καλύτερη επιβεβαίωση ότι επρόκειτο για μία ομάδα με μέλλον. Ο Πρέντραγκ Στογιάκοβιτς επιλέχθηκε στο 14 από τους Σακραμέντο Κινγκς κι αυτό ήταν ουσιαστικά το πρώτο βήμα για να πραγματοποιήσει μία σπουδαία καριέρα στο καλύτερο πρωτάθλημα του κόσμου, ενώ ο Ευθύμης Ρεντζιάς επιλέχθηκε στο 23 από τους Ντένβερ Νάγκετς.