The settlement was founded the 11th century but may have existed as a temporary stop for fisherman from the 9th century. In the 13th century, it became a part of the Novgorod Republic along with the southern part of the Kola Peninsula, and in 1478 was annexed by the Grand Duchy of Moscow. In 1915, the construction of a seaport started, and in 1918 a railroad connecting Moscow to Murmansk running through Kandalaksha was opened. On August 29, 1927, Kandalaksha was made the administrative center of the newly established Kandalakshsky District, and on June 1, 1932, it was granted work settlement status. Status of a town of district significance was granted to it on April 20, 1938. On February 9, 1940, Kandalaksha was administratively separated from the district and granted the status of a town of oblast significance.
In July 1941, during World War II, the town was the primary target of an unsuccessful German-Finnish offensive which attempted to cut the strategic Kirov Railway.
By the Decree of the Presidium of the Supreme Soviet of the RSFSR of March 19, 1959, the Councils of Deputies of Kandalaksha and of Kandalakshsky District were merged into one Kandalaksha Town Council of Deputies. While the district was nominally retained as a separate administrative division, all its subdivisions were administratively subordinated to the town's Council of Deputies.
Since 1995, Vitino oil port operates near Beloye More a few kilometers south of Kandalaksha.
Kandalaksha Mayor Nina Varlamova was murdered in an attack in December 2008.