Mając osiemnaście lat trafił do orkiestry Lenniego Lewisa (zbieżność nazwisk przypadkowa), w której składzie znajdowali się m.in. muzycy z czasowo rozwiązanego big-bandu Duke’a Ellingtona. Z zespołem tym wyjechał do Nowego Jorku i występował w słynnych salach Savoy Ballroom i Apollo Theater. Następnie grał w big-bandzie Boyda Raeburna i przez dłuższy czas w orkiestrach Alvino Reya, Raya Anthony’ego i Texa Benekego, wykonujących muzykę popularną.
Lewis, który uważał się przede wszystkim za muzyka jazzowego, chciał się dostać do orkiestry grającej wyłącznie ten rodzaj muzyki. Był jednak perkusistą mało znanym, a na dodatek działały wówczas tylko cztery znaczące big-bandy jazzowe: Duke’a Ellingtona, Counta Basiego, Woody’ego Hermana i Stana Kentona. Dopiero w 1954 udało mu się dołączyć do orkiestry Kentona (dzięki wcześniejszej rekomendacji Maynarda Fergusona, kolegi z zespołu Raeburna), którą opuścił perkusista Stan Levey. Grał w niej przez dwa lata, podczas których zaprzyjaźnił się z głównym aranżerem Kentona, saksofonistą Billem Holmanem. Obaj założyli wówczas własne combo.