El districte de Kolo és mencionat per primera vegada a les cròniques russes de 1264. La regió fou colonitzada pels pomors, que construïren el fort de Kola el 1565. El segle XVII fou un període de gran prosperitat amb la sortida d'expedicions navals dels pomors cap a Spitzbergen i Nova Zembla.
El HMS Miranda destruint la ciutat de Kola durant la Guerra de Crimea, el 1854.
Kola aconseguí l'estatus de ciutat el 1784, però entrà en una fase de decadència quan Rússia pogué accedir a la mar Bàltica. El govern tsarista aprofità la ciutat per exiliar-hi molts adversaris. Durant la Guerra de Crimea, un navili de guerra britànic bombardejà la ciutat durant vint hores.