Kåre Nordstoga er oppvokst i Notodden hvor han tidlig fikk orgelundervisning av Harald Aune og Odd J. Unhammer. Ved musikkhøgskolen i Oslo studerte han med bl.a. Søren Gangfløt, Bjørn Boysen og Kaare Ørnung, og etter debutkonserten i 1978 videre hos David Sanger i London. Etter en tid som organist Ullern kirke, kom han til Oslo domkirke i 1984. Han er også tilknyttet Norges musikkhøgskole som professor.
I Oslo domkirke fremfører Nordstoga jevnlig et stort orgelrepertoar, bl.a. har han to ganger gitt populære konsertrekker med Bachs samlede orgelverker. Han har i tillegg reist mye i Norge og mange andre land, både som solist og akkompagnatør. Han har spilt inn CD-er med orgelmusikk av Bach, Brahms, Franck, Widor og Liszt, en innspilling med alle Bachs fiolinsonater i samspill med Geir Inge Lotsberg på domkirkens kororgel, og for øvrig flere plater med norsk orgelmusikk. To ganger har han blitt nominert til Spellemannprisen, og for tiden er han i ferd med å fullføre sin innspilling av Bachs samlede orgelverker på historiske orgler i Europa for selskapet Lawo. I 2018 ble hans innspilling av Widors 5. orgelsymfoni fra katedralen i Caen, kåret av BBC Radio 3 til beste innspilling av dette verket, og til komponistjubileet 2022 fullførte han 3 CD-er fra Oslo domkirke med alle orgelverkene av César Franck.
Nordstoga har samarbeidet med folkemusikere som Arve Moen Bergset, Knut Buen og Sinikka Langeland, og har også benyttet folketonestoff i egne orgelverker, nå sist til innvielsen av det nye orgelet i Hamar domkirke 2023.
Nordstoga mottok Lindemanprisen for 2006, Oslo bys kunstnerpris for 2015 og St. Olavs orden i 2016.