Newman nació en Nueva Orleans, Luisiana de Dwight, (pianista) y Louise Newman, una familia musical, teniendo sus primeras lecciones de música con David Jones. Asistió Universidad Estatal de Alabama, donde se unió a la banda universitaria (el Bama State Collegians), se convirtió en su líder e hizo giras con ella.

En 1941 se unió a la banda de Lionel Hampton para dos años, antes de firmar con Count Basie, con quien se quedó un total de trece años, interrumpidos por un periodo largo (1947–1952) en que colaboró primero con el saxo Illinois Jacquet y después con el batería J. C. Heard. Durante su segundo periodo con Basie, que duró aproximadamente nueve años, hizo un gran número de registros como líder de pequeños grupos. También actuó en la orquesta de Benny Goodman en 1962, en la visita a la Unión Soviética.

En 1961 Newman deja la banda de Basie y ayuda a fundar Interacciones de jazz, del cual será presidente en 1967. Su mujer, Rigmor Alfredsson Newman era Directora Ejecutiva. Interacciones de jazz era una organización benéfica qué proporcionaba servicio de información, clases maestras de jazz a escuelas y universidades y más tarde mantuvo su propia Orquesta de Interacción de Jazz (para la qué Newman escribió música).

En los 70 y 80 Newman hace giras internacionalmente y graba para varios sellos importantes. Padece un infarto en 1991 y muere de sus complicaciones en 1992.

• 1954: Joe Newman and His Band (Vanguard)
• 1954: Joe Newman and the Boys in the Band (Storyville)
• 1955: All I Wanna Do Is Swing (RCA Victor)
• 1955: The Count's Men (Jazztone) also released as Swing Lightly
• 1955: I'm Still Swinging (RCA Victor)
• 1956: New Sounds in Swing (Jazztone) with Billy Byers also released as Byers' Guide
• 1956: Salute to Satch (RCA Victor)
• 1956: I Feel Like a Newman (Storyville)
• 1956: The Midgets (Vik)
• 1957: Locking Horns (Rama) with Zoot Sims
• 1957: The Happy Cats (Coral)
• 1958: Soft Swingin' Jazz (Coral)
• 1958: Joe Newman with Woodwinds (Roulette)
• 1958: Counting Five in Sweden (Metronome) also released on World Pacific
• 1960: Jive at Five (Swingville)
• 1961: Good 'n' Groovy (Swingville)
• 1961: Joe's Hap'nin's (Swingville)
• 1961: Joe Newman Quintet at Count Basie's (Mercury)
• 1962: In a Mellow Mood (Stash)
• 196?: Shiny Stockings (Honey Dew)
• 1975: Satchmo Remembered (Atlantic)
• 1977: At the Atlantic (Phontastic)
• 1978: I Love My Baby (Black & Blue)
• 1984: Hangin' Out (Concord)
• 1992: A Grand Night for Swingin': The Joe Newman Memorial Album (Natasha)
• 1994: Jazz for Playboys (Savoy)
• 1999: In Sweden (Jazz Information)
• 2003: Jazz in Paris: Jazz at Midnight (Sunnyside)

Con Manny Albam

• The Drum Suite (RCA Victor, 1956) with Ernie Wilkins
• Brass on Fire (Sold State, 1966)
• The Soul of the City (Solid State, 1966)

Con Gen Ammons

• Twisting the Jug (Prestige, 1961) - with Jack McDuff

Con la Count Basie Orquesta

• The Count! (Clef, 1952 [1955])
• Basie Jazz (Clef, 1952 [1954])
• The Swinging Count! (Clef 1952 [1956])
• Dance Session (Clef, 1953)
• Dance Session Album #2 (Clef, 1954)
• Basie (Clef, 1954)
• Count Basie Swings, Joe Williams Sings (Clef, 1955) with Joe Williams
• April in Paris (Verve, 1956)
• The Greatest!! Count Basie Plays, Joe Williams Sings Standards with Joe Williams
• Metronome All-Stars 1956 (Clef, 1956) with Ella Fitzgerald and Joe Williams
• Hall of Fame (Verve, 1956 [1959])
• Basie in London (Verve, 1956)
• One O'Clock Jump (Verve, 1957) with Joe Williams and Ella Fitzgerald
• Count Basie at Newport (Verve, 1957)
• The Atomic Mr. Basie (Roulette, 1957) aka Basie and E=MC²
• Basie Plays Hefti (Roulette, 1958)
• Sing Along with Basie (Roulette, 1958) - with Joe Williams and Lambert, Hendricks & Ross
• Basie One More Time (Roulette, 1959)
• Breakfast Dance and Barbecue (Roulette, 1959)
• Everyday I Have the Blues (Roulette, 1959) - with Joe Williams
• Dance Along with Basie (Roulette, 1959)
• Not Now, I'll Tell You When (Roulette, 1960)
• The Count Basie Story (Roulette, 1960)
• Kansas City Suite (Roulette, 1960)
• Back with Basie (Roulette, 1962)
• High Voltage (MPS, 1970)

Con Louis Bellson y Gene Krupa

• The Mighty Two (Roulette, 1963)

Con Bob Brookmeyer

• Jazz Is a Kick (Mercury, 1960)
• Gloomy Sunday and Other Bright Moments (Verve, 1961)

Con Ray Bryant

• MCMLXX (Atlantic, 1970) - guest on 1 track

Con Buck Clayton

• Jam Session #1 (Chiaroscuro, 1974)
• Jam Session #2 (Chiaroscuro, 1975)

Con Al Cohn

• Mr. Music (RCA Victor, 1955)
• The Natural Seven (RCA Victor, 1955)
• That Old Feeling (RCA Victor, 1955)
• Four Brass One Tenor (RCA Victor, 1955)

Con Hank Crawford

• Double Cross (Atlantic, 1968)
• Mr. Blues Plays Lady Soul (Atlantic, 1969)

Con Eddie "Lockjaw" Davis

• Count Basie Presents Eddie Davis Trio + Joe Newman (Roulette, 1958) with Count Basie

Con Dexter Gordon

• Swiss Nights Vol. 3 (SteepleChase, 1975 [1979]) - guest on 1 track

Con Freddie Green

• Mr. Rhythm (RCA Victor, 1955)

Con Eddie Harris

• The Electrifying Eddie Harris (Atlantic, 1967)
• Plug Me In (Atlantic, 1968)
• Silver Cycles (Atlantic, 1968)

Con Johnny Hodges

• Sandy's Gone (Verve, 1963)

Con Milt Jackson

• Plenty, Plenty Soul (Atlantic, 1957)

Con Illinois Jacquet

• The King! (Prestige, 1968)
• The Soul Explosion (Prestige, 1969)

Con Quincy Jones

• The Birth of a Band! (Mercury, 1959)

Con Yusef Lateef

• Part of the Search (Atlantic, 1973)

Con Mundell Lowe

• Satan in High Heels (soundtrack) (Charlie Parker, 1961)

Con Junior Mance

• I Believe to My Soul (Atlantic, 1968)

Con Herbie Mann

• Latin Mann (Columbia, 1965)
• Our Mann Flute (Atlantic, 1966)

Con Jack McDuff

• The Fourth Dimension (Cadet, 1974)

Con Gary McFarland

• The Jazz Version of "How to Succeed in Business without Really Trying" (Verve, 1962)
• Tijuana Jazz (Impulse!, 1965) with Clark Terry
• Profiles (Impulse!, 1966)

Con Jimmy McGriff

• The Big Band (Solid State, 1966)
• A Bag Full of Blues (Solid State, 1967)

Con el Modern Jazz Quartet

• Plastic Dreams (Atlantic, 1971)

Con James Moody

• Moody and the Brass Figures (Milestone, 1966)

Con Oliver Nelson

• Oliver Nelson Plays Michelle (Impulse!, 1966)
• Happenings with Hank Jones (Impulse!, 1966)
• Encyclopedia of Jazz (Verve, 1966)
• The Sound of Feeling (Verve, 1966)

Con David "Fathead" Newman

• Bigger & Better (Atlantic, 1968)

Con Buddy Rich

• The Wailing Buddy Rich (Norgran, 1955)

Con Shirley Scott

• Roll 'Em: Shirley Scott Plays the Big Bands (Impulse!, 1966)

Con Sonny Stitt

• Kaleidoscope (Prestige, 1952 [1957])
• Sonny Stitt Plays Arrangements from the Pen of Quincy Jones (Roost, 1955)
• The Matadors Meet the Bull (Roulette, 1965)
• I Keep Comin' Back! (Roulette, 1966)
• The Champ (Muse Records, 1973)

Con Clark Terry y Chico O'Farrill

• Spanish Rice (Impulse!, 1966)

• Ian Carr, Digby Fairweather, & Brian Priestley. Jazz: The Rough Guide. ISBN 1-85828-528-3
• Richard Cook & Brian Morton. The Penguin Guide to Jazz on CD, 6.ª edición. ISBN 0-14-051521-6
• Joe Newman — biografía breve por Scott Yanow, para AllMusic
• " I'm still learning" — Joe Newman entrevistado por Les Tomkins en 1977