Thielemans comenzó su carrera como guitarrista. En 1949 se unió a una jam session en París con Sidney Bechet, Charlie Parker, Miles Davis, Max Roach y otros. En 1949 y 1950 participó en giras europeas con Benny Goodman. Grabó su primer disco en París con su compañero de banda, el saxofonista tenor Zoot Sims. En 1951 se convirtió en miembro de la banda Bobbejaan Schoepen.
Se trasladó a Estados Unidos en 1952. Fue miembro de Charlie Parker's All-Stars y trabajó con Miles Davis y Dinah Washington. Tocó y grabó con Ella Fitzgerald, Jaco Pastorius, Peggy Lee, The George Shearing Quintet, Quincy Jones, Oscar Peterson, Bill Evans, Paul Simon, Billy Joel, The Happenings, Astrud Gilberto, Shirley Horn, Elis Regina y otros.
Un estándar de jazz de Toots Thielemans es "Bluesette", en la que utilizó el silbido y la guitarra al unísono. Grabada por primera vez por Toots en 1962, con letra añadida por Norman Gimbel, la canción se convirtió en un gran éxito mundial. Su forma de tocar la armónica también se puede escuchar en películas como Midnight Cowboy, Jean de Florette, Sugarland Express, The Yakuza, Turkish Delight, The Getaway, French Kiss, Dunderklumpen. Su música también apareció en programas de televisión, como Barrio Sésamo, la serie belga Witse y la serie holandesa Baantjer. ¡Hizo la música de la película sueca de 1974 Dunderklumpen! También puso la voz al personaje animado Pellegnillot.
Su forma de silbar y tocar la armónica se puede escuchar en los anuncios de radio y televisión de Old Spice que se han hecho a lo largo de los años. Durante la década de 1980 actuó con el bajista y compositor/director de banda Jaco Pastorius. En 1983 participó en el álbum An Innocent Man de Billy Joel, y su característica armónica se puede escuchar en "Leave a Tender Moment Alone". Un año después, apareció en la canción de Julian Lennon "Too Late For Goodbyes" del álbum Valotte. En 1984, grabó el último álbum de Billy Eckstine (I Am A Singer). En 1998 publicó un álbum de estilo francés titulado "Chez Toots". Incluía Les Moulins De Mon Coeur (Los molinos de mi corazón) con la participación del cantante invitado Johnny Mathis.
Aparte de su popularidad como músico, era muy apreciado por su modestia y su comportamiento amable. En 2001 Thielemans fue ennoblecido como barón por el rey Alberto II de Bélgica.
