Į kunigus įšventintas 1988 m. arkivysk. Lefebvre'o, kun. Stehlinas paskirtas misionieriauti Gabone, kur praleido 8 metus.
Po šios tarnystės, 1994 m., kunigas paskirtas naujai besikuriančios Šv. Pijaus X brolijos misijos Rytų Europoje vadovu, kuriuo buvo iki 2014 metų. Būdamas čia jis ypatingai nusipelnė ir Lietuvai - 1995 m. jis vienas pirmųjų aukojo tradicines šv. Mišias Vilniuje. Dabartinė (2018 m. atidaryta) Švč. Mergelės Marijos koplyčia Vilniuje - kun. Karlo Stehlino prieš 25 metus pradėtos veiklos tęsėja. Ypatingai mylėdamas Vilnių, kun. Stehlinas ir dabar platina pamaldumą Aušros Vartų Dievo Motinai tolimose pasaulio šalyse. Nuo 2014 metų kun. Stehlinas paskirtas Šv. Pijaus X brolijos Azijos regiono vyresniuoju ir misionieriavo tokiose šalyse kaip Indija, Japonija, Kinija, Filipinai ir t.t., kur pasiekė įspūdingų rezultatų. 2018 m. kunigas vėl paskirtas vadovauti Rytų Europos regionui.
