Mitchell was born on September 20, 1927 in New York City. His younger brother, Whitey Mitchell, also became a jazz bassist.
Mitchell was raised in New Jersey by a father who was an engineer and loved music, and a mother who loved poetry. His first instruments were piano, alto saxophone, and clarinet. Although Cornell University awarded him an engineering scholarship, by 1947 he was in the US Army playing bass. The next year he was in a jazz trio in New York City.
Mitchell became known for performing and/or recording with Mundell Lowe, Chubby Jackson, Charlie Ventura, Woody Herman, Red Norvo, Gerry Mulligan, and, after joining the West Coast jazz scene in the early 1950s, with André Previn, Shelly Manne, Hampton Hawes, Billie Holiday, Stan Seltzer, Ornette Coleman, and others. He also worked as a bassist in the TV and film studios around Los Angeles, occasionally appearing on screen. Mitchell also appeared in documentaries about Tal Farlow, and Zoot Sims.
Saxophonist Harold Land and Mitchell founded and co-led a quintet in the early 1960s. In 1966, Red began tuning his bass in fifths (as the violin, viola, and cello are tuned), and his tuning method opened up many possibilities for bassists.
Mitchell moved to Stockholm in 1968. He won a Swedish Grammy Awards in 1986 and again in 1991 for his recorded performances as a pianist, bassist, and vocalist, and for his compositions and poetic song lyrics.
During this period, Mitchell performed and/or recorded with Clark Terry, Lee Konitz, Herb Ellis, Jim Hall, Joe Pass, Kenny Barron, Hank Jones, Ben Webster, Bill Mays, Warne Marsh, Jimmy Rowles, Phil Woods, Roger Kellaway, Putte Wickman and others. He frequently collaborated in duos, most notably with pianist Kellaway after the mid-1980s.
Returning to the United States in early 1992, Mitchell settled in Oregon where he died at age 65 on November 8, 1992.
A collection of his poetry was published posthumously. His widow is preparing a biography.
- Red Mitchell [Bethlehem] with Conte Candoli, Hampton Hawes, Joe Maini, Chuck Thompson, 1955
- Happy Minors [Bethlehem] with Conte Candoli, Bob Brookmeyer, Claude Williamson, Zoot Sims & Stan Levey, 1955
- Presenting Red Mitchell with James Clay, Billy Higgins, Lorraine Walsh Geller, 1957
- Music for Prancing (1957) with Warne Marsh, Ronnie Ball & Stan Levey on Mode Records (re-released VSOP, 1995)
- Gigi (1958)
- West Side Story (1959)
- Hear Ye! with Carmell Jones, Harold Land, Leon Petties, Frank Strazzeri, 1961
- Adventures for 12-String, 6-String and Banjo, Dick Rosmini, 1964 (as bassist)
- Electronic Sonata for Souls Loved by Nature by George Russell,1969
- Chocolate Cadillac with Horace Parlan, Nisse Sandstrom, Rune Carlsson, Idrees Sulieman, 1976
- Jim Hall and Red Mitchell, Artists House, 1978
- When I'm Singing, 1982, Enja Records
- Simple Isn't Easy, Soloalbum, 1983
- Home Suite, Soloalbum, 1985
- The Red Barron Duo with Kenny Barron, 1986
- Duo with Hank Jones, 1987
- Live at Sweet Basil with Paul Bley (Soul Note, 1988)
- Mitchell's Talking with Ben Riley, Kenny Barron, 1989
- Hear Ye! with Harold Land, Carmell Jones, Frank Strazzeri, Leon Pettis, 1989
- Blaus with Jan "Janka" Johansson, 1992
- Evolution with Lars Jansson, Joakim Milder, 1995
- Live in Stockholm with Roger Kellaway, Joakim Milder, 1995
- Red Mitchell-Warne Marsh Big Two, Vol. 2 with Warne Marsh, 1998
- Live at Port Townsend with George Cables, (1992), 2005
With Gene Ammons
- Gene Ammons in Sweden (Enja, 1973 )
With Chet Baker
- Chet Baker Sings and Plays (Pacific Jazz, 1955)
With Maynard Ferguson
- Dimensions (EmArcy, 1955)
With Ben Webster
- Ben Webster at the Renaissance (Contemporary, 1960)
With J.J. Johnson
- Andre Previn And J.J Johnson Play Kurt Weill (Columbia, 1961)
With Dick Rosmini
- Adventures for 12-String, 6-String and Banjo (Elektra, 1964)
- Leonard Feather (April 5, 1983). "Red Mitchell Brings His Bass Home". Los Angeles Times. Retrieved 2012-09-03. "Red Mitchell, a Swedish resident for 14 years, is getting to spend more and more time back home these days and had to come from New York for his ..."
- "Keith "Red" Mitchell". Orlando Sentinel. November 11, 1992. Retrieved 2012-09-03. "Keith "Red" Mitchell, a jazz bassist who played with such greats as Dizzy Gillespie and Billie Mitchell ..."