The foundations of the city were laid when Erik Axelsson Tott founded the castle of Olavinlinna on the island of Kyrönsalmi in 1475. The castle, named after St Olaf, which was initially also known as the "New Castle", Nyslott in Swedish, was built to protect the eastern border between Sweden and Russia.
A community began to form on the island of Vääräsaari next to the castle, and in 1639 a city charter was granted by Per Brahe, founding the city of Savonlinna.
Development of the city took off in the early twentieth century with the opening of the Olavin Kylpylaitos spa and the birth of a flourishing sawmill industry. The construction of the Saimaa canal and the railway further boosted the city's development. By the start of the twentieth century, Savonlinna was the hub of water-borne traffic on the Lake Saimaa network. The city also started to industrialise in the same period.
Tourism took off after the First World War when spa enthusiasts found Savonlinna a popular destination. The railway link to St Petersburg was already up and running.
In 1973 Sääminki municipality became part of the municipality of Savonlinna. Savonranta municipality merged with Savonlinna in 2009, and Kerimäki and Punkaharju municipalities in 2013.