W następnym roku muzycy zasłynęli nagraniem "The Jazz Messengers at the Cafe Bohemia" a dwa lata później, w 1956 kwintet w składzie: Blakey, Horace Silver, Donald Byrd, Doug Watkins i Hank Mobley nagrał całą płytę dla Columbia Records zatytułowaną po prostu The Jazz Messengers. Po tym jak drogi muzyków rozeszły się w 1957 — Silver, Mobley, Byrd i Watkins utworzyli niezależny kwintet z różnymi, zmieniającymi się perkusistami — Blakey zaadaptował nazwę dla potrzeb swojego projektu ochrzczonego odtąd mianem Art Blakey and the Jazz Messengers.
Dwie konfiguracje muzyków Jazz Messengers zasługują na szczególną uwagę; w obu obok Blakeya najważniejszą rolę odegrał saksofonista Wayne Shorter. W latach 1959–1961 wraz z Blakeyem i Shorterem grali Jymie Merritt, Lee Morgan i Bobby Timmons. W roku 1961 Jazz Messengers stało się sekstetem po tym jak do grupy dołączył puzonista Curtis Fuller a Freddie Hubbard i Cedar Walton zastąpili Morgana i Timmonsa. Shorter przez cały ten okres był dyrektorem artystycznym grupy a wiele z jego kompozycji, jak choćby "Lester Left Town" stało się przebojami na długo kojarzonymi z bandem Blakeya i zagościło na stałe w repertuarze grupy nawet po tym, jak saksofonista opuścił Jazz Messengers.