Pilsēta pirmoreiz minēta 1468. gadā, un apdzīvotās vietas krieviskais nosaukums līdz pat 1918. gadam bija Serdobola (krievu: Се́рдоболь). 1617. gadā, Ingrijas kara rezultātā, apdzīvotā vieta nokļuva Zviedrijas sastāvā. 1632. gadā tā ieguva pilsētas tiesības. Pēc Ziemeļu kara, 1721. gadā, Sortavala iekļāvās Krievijas impērijā, bet 1812. gadā tā tika iekļauta Somijas lielhercogistē. Pēc Krievijas impērijas sabrukuma pēc Pirmā pasaules kara, Sortavala iekļāvās neatkarīgajā Somijā. Ziemas kara rezultātā pilsēta tika iekļauta PSRS, bet pilsētas somu iedzīvotāji evakuējās uz Somiju. Turpinājuma kara laikā no 1941. gada augusta līdz 1944. gada septembrim pilsētu ieņēma somu karaspēks. Pēc kara tā atkal iekļāvās PSRS.