Thielemans begann seine Karriere als Gitarrist. Im Jahr 1949 nahm er an einer Jamsession in Paris mit Sidney Bechet, Charlie Parker, Miles Davis, Max Roach und anderen teil. In den Jahren 1949 und 1950 nahm er an Europatourneen mit Benny Goodman teil. Seine erste Platte machte er in Paris mit seinem Bandkollegen, dem Tenorsaxophonisten Zoot Sims. Im Jahr 1951 wurde er Bandmitglied der Bobbejaan Schoepen.
Er zog 1952 in die USA. Er war Mitglied der All-Stars von Charlie Parker und arbeitete mit Miles Davis und Dinah Washington zusammen. Er spielte und machte Aufnahmen mit Ella Fitzgerald, Jaco Pastorius, Peggy Lee, dem George Shearing Quintet, Quincy Jones, Oscar Peterson, Bill Evans, Paul Simon, Billy Joel, The Happenings, Astrud Gilberto, Shirley Horn, Elis Regina und anderen.
Ein Jazz-Standard von Toots Thielemans ist "Bluesette", bei dem er Pfeifen und Gitarre unisono einsetzte. Erstmals 1962 von Toots Thielemans aufgenommen, wurde das Lied mit den von Norman Gimbel hinzugefügten Worten zu einem großen Welthit. Sein Mundharmonika-Spiel ist auch in Filmen wie Midnight Cowboy, Jean de Florette, Sugarland Express, The Yakuza, Turkish Delight, The Getaway, French Kiss, Dunderklumpen zu hören. Seine Musik war auch in Fernsehsendungen zu hören, unter anderem in der Sesamstraße, der belgischen Fernsehserie Witse und der niederländischen Fernsehserie Baantjer. Er komponierte die Musik für den schwedischen Film Dunderklumpen! von 1974. Er sang auch die Zeichentrickfigur Pellegnillot.
Sein Pfeifen und Mundharmonikaspiel ist in Radio- und Fernsehspots von Old Spice zu hören, die im Laufe der Jahre entstanden sind. In den 1980er Jahren trat er mit dem Bassisten und Komponisten/Bandleader Jaco Pastorius auf. 1983 war er auf dem Album An Innocent Man von Billy Joel zu hören, und sein Markenzeichen, die Mundharmonika, ist auf "Leave a Tender Moment Alone" zu hören. Ein Jahr später erschien er auf dem Julian-Lennon-Song "Too Late For Goodbyes" aus dem Album Valotte. 1984 nahm er das letzte Album von Billy Eckstine (I Am A Singer) auf. 1998 veröffentlichte er ein Album im französischen Stil mit dem Titel "Chez Toots". Es enthielt Les Moulins De Mon Coeur (Die Mühlen meines Herzens) mit Gastsänger Johnny Mathis.
Abgesehen von seiner Popularität als Musiker war er wegen seiner Bescheidenheit und seines freundlichen Auftretens sehr beliebt. Im Jahr 2001 wurde Thielemans von König Albert II. von Belgien zum Baron geadelt.
