Holley attended the prestigious Cass Technical High School. Holley played violin and tuba when young and started playing bass while serving in the Navy. In the latter half of the 1940s he played with Dexter Gordon, Charlie Parker, and Ella Fitzgerald; in 1950 he and Oscar Peterson recorded duets, and he also played with Peterson and Charlie Smith as a trio. He was married to Minnie (Millicent) Walton née Aitcheson.
In the mid-1950s he moved to England and worked at the BBC. Upon his return to America he toured with Woody Herman in 1958 and with Al Cohn/Zoot Sims in 1959-60. A prolific studio musician, he played with Duke Ellington in 1964 and with the Kenny Burrell Trio, Coleman Hawkins, Lee Konitz, Roy Eldridge, Michel Legrand, Milt Buckner, Jay McShann and Quincy Jones in the 1960s and 1970s. From 1967 to 1970 he taught at the Berklee College of Music.
Holley was noted for singing along with his arco (bowed) bass solos, a technique Slam Stewart also used. Holley and Stewart recorded together on two albums in the 1970s.
- As sideman
- Dicky Wells - Bones for the King (Felsted, 1958)
- Dicky Wells - Trombone Four-in-Hand (Felsted, 1959)
- Richie Pratt - Olathe (Artists Recording Collective, 2007)
- Kenny Burrell - Bluesin' Around (Columbia, 1962 ), Bluesy Burrell (Moodsville, 1962), Midnight Blue (1963)
- Coleman Hawkins - Hawkins! Eldridge! Hodges! Alive! At the Village Gate! (Verve, 1962), Hawkins! Alive! At the Village Gate (Verve 1962), Good Old Broadway (Moodsville, 1962), The Jazz Version of No Strings (Moodsville, 1962), Coleman Hawkins Plays Make Someone Happy from Do Re Mi (Moodsville, 1962), Desafinado (Impulse!, 1962), Back in Bean's Bag (Columbia, 1963) – with Clark Terry
- Stanley Turrentine - Never Let Me Go (1963)
- Milt Jackson - For Someone I Love (Riverside, 1963)
- Rufus Jones – Five on Eight
- Quincy Jones - Quincy Jones Explores the Music of Henry Mancini (1964)
- Roland Kirk - Here Comes the Whistleman (1965)
- Johnny Guarnieri - Johnny Guarnieri Originals (1979)
- Frank Sinatra - L.A. Is My Lady (1984)
- Shirley Scott - The Soul Is Willing (Prestige, 1963), Drag 'em Out (Prestige, 1963)
- Jaki Byard - Family Man (Muse, 1978)
- Dave McKenna - Dave McKenna Quartet with Zoot Sims (Chiaroscuro, 1974)
- Teddy Wilson - Teddy Wilson and his All-Stars (Chiaroscuro, 1976)
- Flip Phillips - The Claw (Chiaroscuro, 1986)
- Jay McShann - Some Blues (Chiaroscuro, 1992)
- Totti Berg - " Major Blues" Gemini records 1990
- Scott Yanow, Major Holley at Allmusic. Retrieved 2 May 2013.
- "Mule Holley, Bassist, Dead at 66; A Favorite Among Jazz Musicians", The New York Times