Kirkenes Airport (KKN), 15 km west of town, has direct flights to Oslo on Widerøe and SAS — journey time around two and a half hours. Widerøe also flies in from Tromsø, Alta, and other northern Norwegian towns. Taxis meet flights; there is no bus service.
The other option — and for many travellers the point — is the Hurtigruten coastal ferry from Bergen. The northbound voyage takes roughly six days along the length of Norway's coastline, stopping at 34 ports; Kirkenes is the final stop. The return south departs the same evening. Book well ahead in winter.
There is no road border crossing with Russia at Storskog for non-residents of the border zone; crossing requires a Russian visa and a specific permit. The crossing is straightforward if the paperwork is in order but is not a casual day-trip option.