1991-2004: Η αναγέννηση και η... πτώση
Μετά τα πέτρινα χρόνια της δεκαετίας του ’80, ήρθε η δεύτερη χρυσή δεκαετία του Θρύλου. Το 1991, ο Σωκράτης Κόκκαλης ανέλαβε τα ηνία και οδήγησε την ομάδα στην κορυφή της Ελλάδας και της Ευρώπης.
Πέντε συνεχόμενα πρωταθλήματα (1993, 94, 95, 96, 97), τρία κύπελλα (1994, 97, 02) και βεβαίως το Κύπελλο Πρωταθλητριών στο Φάιναλ Φορ της Ρώμης (1997) είναι το επιστέγασμα μιας εντυπωσιακής πορείας του Ολυμπιακού που έπαιξε ακόμη σε δυο ευρωπαϊκούς τελικούς (1994, 1995) στα τέσσερα Φάιναλ Φορ που αγωνίστηκε (1999 - 3η θέση).
Δυο μεγάλοι προπονητές, ο Γιάννης Ιωαννίδης και ο Ντούσαν Ίβκοβιτς κάθισαν στον πάγκο. Ενώ παίκτες παγκόσμιας εμβέλειας όπως οι Πάσπαλι, Ρίβερς, Τζόνσον, Τάρπλεϊ, Βολκόφ, Ράτζα, Καρνισόβας, Κόματζετς, Τάρλατς, Τόμιτς μαζί με τους μεγάλους Έλληνες παίκτες όπως οι Φασούλας, Καμπούρης, Σιγάλας, Μπακατσιάς έχτισαν την «ερυθρόλευκη» Αυτοκρατορία.
Τη σεζόν 2001-02 με τον Λευτέρη Σούμποτιτς στον πάγκο ο Ολυμπιακός επέστρεψε στους τίτλους ύστερα από πέντε χρόνια, κατακτώντας το Κύπελλο Ελλάδας και έχοντας για μεγάλο πρωταγωνιστή τον αείμνηστο Αλφόνσο Φορντ. Αυτός ο τίτλος ήταν και ο τελευταίος για την εποχή Κόκκαλη στον μπασκετικό Ολυμπιακό. Την επόμενη χρονιά, ο Ολυμπιακός έφτασε μια ανάσα από το Φάιναλ Φορ.
Την κατάκτηση του κυπέλλου Ελλάδας το 2002, τη χαμένη ευκαιρία για την πρόκριση στο Φάιναλ Φορ της Μπολόνια και το χαμένο τελικό του πρωταθλήματος από την ΑΕΚ, ακολούθησαν δύσκολα χρόνια. Το μπάτζετ της ομάδας μειώθηκε σημαντικά αλλά το πνεύμα νικητή δεν χάθηκε.
Το ρόστερ των «ερυθρόλευκων» άλλαξε και με ηγέτες του Τόμιτς και Μορίς Έβανς ο Ολυμπιακός έφτασε και πάλι μια ανάσα από το Φάιναλ Φορ αλλά η Μπαρτσελόνα που τελικά κατέκτησε τον τίτλο τον απέκλεισε στις λεπτομέρειες.
Οι σεζόν 2003-04 και 2004-05 ήταν πολύ δύσκολες. Το καλοκαίρι του 2004 ο Σωκράτης Κόκκαλης ανακοινώνει ότι αποχωρεί από την ομάδα και με τον Μίλαν Τόμτς στην άκρη του πάγκου οι «ερυθρόλευκοι» προσπαθούν να χτίσουν μια ομάδα με αξιοπρέπεια. Το φθινόπωρο του ίδιου έτους όμως ο Σωκράτης Κόκκαλης επιστρέφει και μαζί του ο Παναγιώτης και ο Γιώργος Αγγελόπουλος. Είναι δύσκολο όμως να αλλάξει το χαμηλής δυναμικότητας ρόστερ που είχε δημιουργηθεί εκείνο το καλοκαίρι.