En 1946 se unió a la orquesta de Gene Krupa como arreglista, siendo el compositor del éxito ''Disc Jockey Jump''.

Las primeras interpretaciones notables en el saxo barítono las realizó como miembro del Miles Davis Nonet entre 1948-50.

Para tal fin, el trompetista reunió a un conjunto heterogéneo conformado por boppers destacados (Max Roach, John Lewis, él mismo) y algunos de los principales músicos de Thornhill (Gerry Mulligan, Lee Konitz y Bill Barber).

Esto hizo que Capitol Records relanzara años más tarde las grabaciones del noneto bajo el nombre Birth of the Cool, y que su trabajo llegase a ser considerado un hito en la historia del jazz.

En 1952, se radicó en Los Ángeles, donde pronto destacó escribiendo arreglos para la prestigiosa orquesta de Stan Kenton ("Youngblood", "Swing House", "Walking Shoes") y dando conciertos en el club The Haig.

La sección rítmica se completó con Chico Hamilton en la batería y Bob Whitlock, en el contrabajo.

Particularmente exitosa fue la grabación de My Funny Valentine, que Baker convirtió en su canción insignia y fue introducida en 2015 al Grammy Hall of Fame.

El cuarteto original llegó así a un abrupto final, pero sus trabajos siguieron publicándose y reeditándose en los años siguientes.

Tras salir de prisión, Mulligan buscó reanudar el cuarteto original, pero tuvo problemas para negociar con Baker, quien había comenzado una carrera estelar en solitario que lo llevaría a convertirse en uno de los jazzmen más codiciados en la industria del espectáculo.

[5]​ El trombonista Bob Brookmeyer ocupó el lugar para formar un nuevo cuarteto que, sin alcanzar las notas de creatividad del original, continuó difundiendo la música de Mulligan mediante exitosas giras por Europa y Estados Unidos.

Tras realizar una serie de álbumes en solitario, que abarcaron desde su ya clásico cuarteto sin piano hasta la incursión en el bossa nova en Night Lights, se unió al conjunto de Dave Brubeck sustituyendo a Paul Desmond.

Formó una nueva orquesta con la que ganó en 1982 el Grammy al mejor álbum jazz conjunto por Walk on the Water.