Pastorn var dömd till livstids hårt straffarbete anklagad för ”omstörtande verksamhet”. Han har nu släppts av humanitära skäl, enligt den statliga nyhetsbyrån KCNA.
En kanadensisk delegation har varit på plats i Pyongyang för att diskutera fallet.
”Kanadas regering har aktivt engagerat sig i herr Lims fall på alla nivåer. Jag vill speciellt tacka Sverige, vår skyddsmakt i Nordkorea, för att man hjälpt oss”, säger Justin Trudeau i ett uttalande, och tillägger att man inte kan säga så mycket mer om arbetet med fallet.
LÄS MER: Nordkorea släpper kanadensisk pastor
Läggs in på sjukhus
Hyeon Soo Lim är född i Sydkorea och är pastor i en kyrka i Toronto. Han dömdes i december 2015 efter att då ha suttit fängslad sedan i februari. Han har i statliga medier, förmodligen under tvång, erkänt brott mot staten.
Lim väntas återvända till Kanada på torsdagen och kommer att läggas in på sjukhus direkt vid ankomst, på begäran av hans fru, enligt en källa.
– Det har bekräftats att kanadensiska tjänstemän och läkare flyger med pastor Lim, säger källan.
I uttalandet från premiärministerns kansli säger Trudeau att Kanada kommer att se till att får vård, och att han väntas återförenas med familj och vänner ”snart”.
Amerikaner fängslade
Lims familj har blivit allt mer oroliga för hans hälsa efter fallet med den amerikanska studenten Otto Warmbier. Han dömdes i fjol till 15 års fängelse i Nordkorea och återvände till USA i juni, i koma. Han avled efter några dagar i hemlandet.
LÄS MER: Amerikanske studenten Otto Warmbier har avlidit
I Nordkorea sitter fortfarande tre amerikanska medborgare fängslade. Ett förbud för amerikaner att resa till landet träder i kraft den 1 september på grund av risken att bli kvarhållen i diktaturen.
Sverige är skyddsmakt även åt USA och har tidigare besökt flera amerikanska fångar i Nordkorea. Vita huset har vid flera tillfällen tackat Sverige för hjälpen med att få fångar frisläppta från landet.