Постоји неколико верзија о датуму оснивања Коле, а најстарија верзија је да је град основан1264. године. Тај датум је оспорио професор Иван Ушаков по којем је град основан знатно касније,1565. године. Савремени руски историчари тврде да је град настао вероватно пре1517. године, а своје тврдње базирају на неким од докумената датираних на то време, а у којима књазВасилиј III Иванович између осталих, међу насељима на северу помиње и Колу. Међутим сам податак није поуздан јер име Кола може да се односи и на Колдонску тврђаву која је постојала у то време. У сваком случају2015. прослављено је 450 година од оснивања Коле.
У сваком случају Кола је основана као утврђење на острву окруженом рекамаКолом иТуломом и обаломКољског залива. Становништво је било оријентисано на риболов и трговину, а од најранијих времена кољско становништво је одржавало живе трговачке везе са холандским, шведским и норвешким трговцима. Током 70-их и 80-их годинаXVI века захваљујући трговини Кола је постала важно међународно трговачко средиште где се трговало рибом и крзнима. Крајем XVI и почеткомXVII века Кола је била јако утврђено насеље и једно од највећих утврђења на руском северу.
Са почеткомВеликог северног рата1700. измеђуРусије иШведске почињу учестали напади Швеђана на руске територије на северу. По налогу императораПетра Великог сва стратешка ансеља на северу морала су додатно да се утврде, па је сходно томе и кољска тврђава додатно ојачана. Године1708. Русија је подељена на губерније, а дотадашњи Кољски округ улази у састав Архангељске губерније.
Дана6. фебруара1780. Кола је званично проглашена градом у саставу Вологодског намесништва, а четири године касније проглашена је окружним центром Архангељске губерније. У границе Кољског округа укључени су и селаВарзуга иУмба. Први грб града усвојен је2. октобра1781. године.
ИмператоркаКатарина Велика је27. фебруара1783. граду Коли поклонила 8.000 рубаља за градњу камене цркве. Храм посвећен Благовештењу саграђен је у периоду1804−1807. године. У периоду од маја до августа1826. године, експедиција под вођствомМихаила Рејнекеа извршила је детаљно описивање Кољског залива, док је 1830. у Санкт Петербургу издата књига „Опис града Коле из руске Лапоније” (рус.«Описание города Колы в Российской Лапландии»). Прва парохијска школа у граду основана је31. марта1839. године, а била је то уједно и прва школа на целомКољском полуострву.
У нападима енглеске артиљерије са корвете „Миранда”1854. године изгорео је највећи део града, а уништена је тврђава и Воскресењски саборни храм. Након тога долази до великог застоја у развоју града, Кољски округ је распуштен, а сам град деградиран у статус провинцијског. Становништво почиње да се враћа назад у град тек од лета1855. године.
Према статистичким подацима из1866. град је имао 734 становника и 96 грађевина. У јануару1878. у граду почиње да делује метеоролошка станица, прва на целом Кољском полуострву. Кољски округ са седиштем у Коли поново је успостављен у фебруару1883. године.
У првим деценијама20. века град константно стагнира, број становника се смањује и све то је довело до тога да Кола1926. буде деградирана у ранг села. Статус урбаног насеља поново добија1935. године, а од1965. поново има званичан статус града.
Према подацима са пописа становништва2010. у граду је живело 10.437 становника, док је према проценама националне статистичке службе за2016. град имао 9.735 становника.[1]