The first documented mention of the town itself dates to 1565—[7] the area was settled by the Pomors, who built the fort of Kola also called Malmus (Russian: Мальмус).

Although it was incorporated as a town in 1784, Kola declined after Russia gained access to the Baltic Sea, and was used by the Tsarist government as a place of exile.

[7] Kola was destroyed by a twenty-hour bombardment in 1854[7] by a three-ship squadron led by the Royal Navy sloop HMS Miranda, at the time of Crimean War.

On October 16, 1925—when the Murmansk Governorate Commission meeting initiated work on compiling the lists of the urban and rural localities—Murmansk, Alexandrovsk, and Kola were categorized as urban; however, a recommendation was sent to the All-Russian Central Executive Committee (VTsIK) to demote the latter two to rural localities due to economic conditions, sparse population, low trade volume, lack of industrial enterprises, and "general regress".

[11] The plan was not confirmed by the Leningrad Oblast Executive Committee,[11] but Kola was re-classified as an urban locality by the VTsIK Resolution of August 20, 1935, when it was granted work settlement status.