Murmansk is very accessible on foot. Distances aren't very big so you can easily walk. The polluted air might make it a little less attractive to do so and ofcourse when the weather is bad, you might want to catch a bus or taxi!
Go to Murmansk by train! It's a long ride but it's such a great expirience! Very cheap and quite comfortable. From St-Petersburg 29 hours and 40 hours from/to Moscow. Spend your evening or day looking out the window; the senery is gorgeous! Untouched wilderness of deep green pinetrees and wild white rivers. This is a good way of discovering the wonderful vegetation on the Kola peninsula.
a) by plane: direct flights from many russian cities, flights to Rovaniemi (FIN), and to Kirkenes and Tromsö (N)
b) by bus: from Ivalo (FIN) 6 1/2h on partly unsealed roads (Muurmanskekspress Gold Line, tel. 00358 16 334 55 21; see the sloppy machine at the russinan-finnish border on the pic!), or from Kirkenes (N) 5h
c) by train: daily connections from Moskva and Sankt-Peterburg, direct carriages to many other cities.
by bus and train you can easily explore the whole region
From Moscow or St. Petersburg:
The best way to get to Murmansk from other places in Russia is by train - it's comfortable and very cheap. The trains have sleeping compartments (2- and 4-berth) and a restaurant car. The travel time by train to Murmansk is 27-29 hours from St. Petersburg and 36-40 hours from Moscow, but you see a lot on the way, and you can talk with other people in the compartment. The train fare Moscow-Murmansk US$27 in 4-berth sleeper, the train fare St Petersburg-Murmansk is US$21 in 4-berth sleeper.
From northern Norway:
There's a bus from Kirkenes (Norway) to Murmansk 6 times weekly (daily except Saturday), which takes about 4 hours. The fare isUS$40 one-way.
Murmansk is on the edge of Europe, of course. Nevertheless it's not too difficult to get there. There are daily flights from Moscow and St. Petersburg to Murmansk by Aeroflot. Between Norway and Murmansk there are flight connections from Tromsoe by Aeroflot and from Kirkenes by Arctic Air.
As well you can get by scheduled bus connections from Kirkenes (Norway) to Murmansk - this is the way I took. The bus needs about 4-5 hours - depending on time to cross the border. The bus leaves Kirkenes at 2 pm local time and arrives in Murmansk at about 8pm local time - the time shift is 2 hours between Norway and Russia, back to Norway leaves the bus at 8am in Murmansk and arrives at about 11.30am. The bus ticket costs about 30 USD per direction and person - the flying ticket about 120 USD per direction and person. In Winter it's not so beautiful to take the bus in the afternoon, because it's dark and you see nothing. But the bus connection in the morning is very beautiful.
You can also come by train to Murmansk - there's a line from St. Petersburg to Murmansk - I wasn't there, but it must be a very beautiful setting along this route.
Murmansk has many city bus lines and electric bus lines. Fares are low. But it's not easy to use the bus, you must be able to read kyrillic letters. Drivers don't tell the stations. Buses are very crowded. Murmansk has also trains to get in the neighbour towns - you can buy the very cheap tickets right in the train station. In the town of Murmansk it's the best to walk or to use taxis - but be careful (see: Warnings).
We flew from Moscow - excellent views of the countryside on the way up - you really get an idea of just how vast and empty the landscape is.
The centre of town is easy to walk around, but we were lucky in finding one of those indispensible taxi drivers - we had two Kiwis with us and he had served with the Merchant Navy off New Zealand, so we were instant friends and he was able to help us organise chartering a boat to cruise up the river.
Murmansk station is the Terminal of the railway from the east to west, from south to the North... It takes about 36 hours to arrive from Moscow.
The besy way to get around the city is the trolleybus, which runs along the main street, Prospekt Lenina. It's frequent and very cheap.