Debüteeris 16-aastaselt oma džässtrioga 1967. aastal Tallinnas legendaarsel rahvusvahelisel džässifestivalil Tallinn 1967. Järgmisel aastal salvestas oma esimese LP – ”Tõnu Naissoo Trio”. Esimesed sooloklaverietteasted tegi Tõnu Naissoo 1971. aastal Venemaal – Novgorodis ja Leningradis. Aastatel 1972–1976 mängis show-ansambli Laine saatebändis. 1977. a alustas tegevust tema teine trio, millega esines edukalt 1978. a Thbilisi džässifestivalil. 1980. a salvestas oma teise albumi – “Turning Point” – plaadifirma Melodija all. 70ndate teises pooles ja 1980ndatel jätkus kontserttegevus aktiivselt NSVLi liiduvabariikides, esinedes nii soolopianistina kui ka oma trio ja kvartetiga Lätis, Leedus, Valgevenes, Ukrainas, Moldaavias, Gruusias, Aserbaidžaanis ning Leningradis ja Moskvas. 1980ndatel lisandusid välisesinemised Ungaris, Kuubal, Soomes, Inglismaal, Iirimaal, Saksamaal, Belgias ja Prantsusmaal. 1989–1990 oli stipendiaat Berklee Muusikakolledžis USA-s. 

On osalenud pianistina sellistes rahvusvahelistes projektides nagu EBU Big Band (Pori Jazz, 1985), Trio Thomas Eckert – Vjatšeslav Gaivoronski – Tõnu Naissoo (Turku Jazz, 1992), The Baltic Trio (Schleswig-Holstein Musik Festival, 1992), Vladimir Tarasov’s Baltic Art Orchestra (Jazz Baltica ja Münsteri džässifestival, 1994). 2002. aastal esines Praha 6. džässpianistide festivalil, mängides samal kontserdil koos Adam Makowiczi ja John Tayloriga. 2000ndate esimesel kümnendil esines koos  George Haslami “FreeTime” impro-muusikagrupiga Prahas ja teistes Tšehhi Vabariigi linnades. On teinud kuus kontserttuuri Jaapanis ja viimasel ajal esinenud taas Venemaal – Moskvas, Peterburis, Jaroslavlis, Arhangelskis ja Severodvinskis. 

Klassikalise muusika vallas on ühe solistina kaasa teinud Alfred Schnittke 1. sümfoonia ettekandel Leningradis NSVL-i Kultuuriministeeriumi SO-ga (1987), esiettekannetel USA-s Bostoni SO-ga (1988) ja Hollandis Rotterdami Filharmoonia Orkestriga (1991). 1994. a esines koos Riia Keelpillikvartetiga kaasaegse muusika festivalil Riias Wagneri Kontserdimajas.

On esinenud sellistes kuulsates kontserdisaalides nagu Boston Symphony Hall USA-s, De Doelen Rotterdamis, Rudolfinum Prahas, Tšaikovski kontserdisaal Moskvas, Kapell Peterburis ja Orchard Hall Tokyos.

Stiililiselt hõlmab tema mäng džässi erinevaid tahke – mainstream’i, post-pop’i, jazz-rock’i ning free-jazz’i. Sooloklaverikontsertidel esitab ka vabu improvisatsioone.

Peale džässkompositsioonide on kirjutanud muusikat 50 filmile ja 20 teatri-ja TV-lavastusele ning reklaamfilmidele.

Eri koosseisudega on andnud välja 30 sooloplaati, neist enamik Jaapani Atelier Sawano label’i all ning viimasel ajal ka Moskva firma ArtBeati Musicu väljaantuna.

On olnud 30 aastat tegev pianistina hotellis Viru (1976–2005).