Joe Newman vivió en sus comienzo la magia del swing al lado de su padre, trompetista de los "Creole Serenaders" en los mejores tiempos del barrio de Storyville en New Orleáns. Cuando la decadencia llegó hasta allí, Joe se trasladó a New York para incorporarse a la banda de Lionel Hampton con quien estuvo dos años. En diciembre de 1943 ingresó en la orquesta de Count Basie en la que militó con esplendor en dos etapas: la primera entre 1943 y 1945, cuando coincidió en la bigband con Buddy Tate, Illinois Jacquet, o Buck Clayton; y la segunda entre 1951 y 1960 donde junto a Harry Sweets Edison formó un dúo inolvidable en la sección de metales de Count Basie.

     Las grabaciones de Joe Newman, tanto en la formación de Basie, como posteriormente en la de Buck Clayton fueron numerosas y extraordinarias, destacando también en la faceta de compositor. Sus discos a su nombre se dieron básicamente en el transcurso de varias giras europeas, especialmente en su participación en la "Grande Parade du Jazz" de Niza donde era invitado con asiduidad. Newman tuvo el merito de crear su propio estilo a la trompeta basado en un lenguaje tradicional y moderno  la misma vez. Nunca cayó en la comercialidad y aunque coincidió con grandes trompetistas contemporáneos como: Buck Clayton, Harry Sweets Edison o Eddie Davis, supo ganarse el respeto de sus colegas. 

     En 1962 viajó a Moscú acompañando a la banda del clarinetista, Benny Goodman para dar el primer concierto de jazz en la extinta Unión Soviética. Diez años mas tarde participó en una memorable grabación en el Festival de Jazz de Newport y al año siguiente fue contratado por Benny Carter para una gira por Europa. en los ultimos años de su carrera formó parte de la gran orquesta "Basie Alumni" formada íntegramente por ex músicos del gran pianista y líder de una de las grandes bandas de swing de la historia, el maestro Count Basie. La discografía a su nombre es extensa y de calidad y se desarrolló básicamente en los sellos: Vanguard, Savoy, Roulette, Swingville, Concord y MCA donde grabó en 1958 el álbum "Jazz Heritage: Joe Newman Quartet/Shirley Scott" uno de los mas aplaudidos de su carrera.