Beboelse på området har eksisteret siden det 11. århundrede. I det 13. århundrede blev den en del af republikken Novgorod, sammen med den sydlige del af Kolahalvøen, og i 1478 blev den annekteret af Rusland.
I 1915 påbegyndtes konstruktionen af en havn, og i 1918 blev jernbanen mellem Moskva og Murmansk, som stopper i byen, åbnet.