Alussa se ei ollut kuin puinen varustus, joka ensi hätään laitettiin Savonmaan suojelukseksi. Vaan kaksi vuotta myöhemmin vahvempi kivinen linna rakennettiin sijaan. Tott hankki 16 taitavaa muurimestaria ulkomailta; sillä kivisten linnain rakentaminen ei ollut kotiteollisuutta Suomenmaassa. Hän lähti itse sinne asemiehinensä, rakennustyötä varjelemaan; sillä Venäjän Karjalasta tehtiin alituisia rynnäköitä ja viholliset olivat joka paikassa väijyksissä. Joka kerta, milloin työväki pantiin lotjilla tuomaan hiekkaa, kiviä ja kalkkia, täytyi kuhunkin alukseen panna parvi sotaväkeä ja 12 tai 14 Totein omia ritarillisia palvelijoita täysissä aseissa ja haarniskoissa. Se oli melkein niinkuin Jerusalemin muurien rakentaminen Nehemian aikana.
Näin nousi linnan kivinen muuri; tornit kohosivat, kuvastuen Kyrönsalmen syviin aaltoihin; muut tarpeelliset huoneet, kellarit ja vara-aitat varustettiin. Mutta maallisen vahvuuden ohessa tarvittiin taivaallisten valtain suojelus. Tuo pohjoisilla mailla kuuluisa ja kunnioitettu pyhimys, Norjan muinainen kuningas Olavi, valittiin linnan suojeluspyhäksi, ja Savon varustukselle annettiin nimi "Pyhän Olavin linna". Vaan itsellensäkin oli Eerik Akselinpoika tässä nostanut muistopatsaan. Muutaman käytävän seinään vastapäätä "kuninkaan-salia" hän antoi muurata kivisen taulun, jossa luettiin näin kuuluva kirjoitus:
"Anno 1475 minä Eerik Akselinpoika Ritari rakennutin tämän linnan, Jumalalle ylistykseksi, pyhälle Kristin-uskolle vahvistukseksi. Silloin vaimoni nimi oli Elina Kustaantytär Lagmansöö'n rouva".
Tämän seinäkirjoituksen yläpuolella olivat aviopuolisojen vaakunat, nimittäin Stuure-vaakuna ja Tott-vaakuna.
Uuden linnan suojassa alkoi uudis-asutus näillä tienoilla vahvistua; Säämingissä syntyi Savon kolmas seurakunta, ja muinais-taru kertoo Eerik Akselinpojan tuoneen ruotsalaisiakin asukkaita uuden voittomaan vahvistukseksi. Pian sen jälkeen Eerik Akselinpoika kuoli Viipurissa v. 1480. Vähän aikaa nyt oli rauhallisemmat menot rajan puolella. Mutta sodan myrsky-pilvet kokoontuivat yhä synkemmiksi, kunnes v. 1495 puhkesivat hirveään tuuliaispäähän. Iivana väitti, eikä aivan syyttä, että Pähkinäsaaren rauha oli rikottu. Raja oli siirretty itään päin, uusi linna oli vastoin rauhansovintoa näille maille rakennettu, vieläpä rakennettu semmoiseen paikkaan, jonka tsaari luki omaksi alueeksensa. Näin ollen pitäisi ruotsalaisten muka antaa takaisin nuo kolme Karjalan kihlakuntaa, mitkä olivat ennen muinoin ystävyydenlahjaksi saaneet. Semmoinen oli Iivanan ajatus, ja hänen todistajanansa oli 60,000 miehen armeija, joka vyörytettiin Viipuria vastaan. "Viipurin pamaus" tosin pelasti tämän tärkeän rajalinnan, mutta sota levisi pitkin koko valtarajaa perimmäiseen pohjaan asti. Nytpä vasta saatiin kokea, minkä hyvän työn Tott oli Savonmaalle tehnyt. Venäläinen parvikunta karkasi tähänkin maakuntaan; mutta Savonlinnan vouti, Pietari Niilonpoika, lähti ritaripalvelijain ja rahvaan kanssa vihollista vastaan ja karkoitti päällekarkaajat rajan yli. Seuraavana talvena tuli isompi voima, joka alkoi linnaa piirittää. Steen Stuure, joka nyt oli Suomeen tullut, oli siihen aikaan lähettänyt Olavinlinnan vahvistukseksi 70 huovia, ja nämä, jotka eivät aavistaneet vihollisten sitä silloin saartavan, joutuivat melkein kaikki venäläisten käsiin. Mutta linna Kyrönsalmessa ei kumminkaan kukistunut; Tott'in takoma lukko ei särkynyt — ja Ruotsin valta Savossa säilyi.
Savonlinnan ihmeet.
Olipa kummallinen seutu tuo rajalinnan paikka erämaiden liepeessä.
Näin kertoo Olaus Magnus, Upsalan entinen arkkipiispa, joka on lähtenyt uskonpuhdistusta pakoon eteläisille maille ja siellä julkaisee kuvallisen maantietonsa Ruotsin valtakunnasta, sen kansoista ja luonnon-ilmiöistä.
Kaukana perimmäisessä Suomenmaassa, mutta Ruotsin vallan alueella, on linna, joka Uudeksi linnaksi nimitetään. Se on ihmeteltävällä nerolla rakennettu, kerrassaan luonnon ja taiteen vahvistama, seisoen ympyriäisen kallion päällä. Yksi ainoa portti siitä viepi länttä kohden; portin edustalla on lautta-silta, vahvoilla rautavitjoilla kiinnitettynä, ja tämä aina yöksi vedetään koneiden avulla rantaan, — tosin ankaralla vaivalla väkevän virran tähden. Tuo leveä joki, joka siitä ohitse kulkee, on syvyydeltään tutkimaton. Se tulee kaukaisista järvistä, Vienan "valkoisesta" merestä saakka; vaan linnan kohdalta se on mustapohjainen, ja kaikki kalat, jotka siinä syntyvät ja elävät, lohet ja taimenet, hauet ja ahvenet sekä muut pehmeälihaiset kalat, ovat ihan mustia, mutta kuitenkin hyviä maultaan. Lahnakin siinä virrassa on kesällä musta, vaikka talvella valkoinen. Ja kun joki sitten purkautuu, kulkien Viipurin ohitse, se muuttaa itse järvenkin mustaksi.
Muitakin kummia täällä toisinaan nähdään. Kova on isännyyden virka täällä vihollisvallan kynnyksellä, kova myöskin laki, jonka alaisena linnan väki elää. Jos vartija nukkuu asemaansa, hän syöstään säälimättä tornin harjalta virtaan. Surma ja perikato ovat siis aina tarjona sekä päällikölle että hänen miehillensä. Mutta jokaisen onnettomuuden edellä käypi kummallinen aave. Silloin, näet, ilmestyy virran aaltojen päälle neitonen, joka kanteleen viehättävällä soitolla yön hiljaisuutta häiritsee, ikäänkuin seireenien tavalla houkutellen ihmis-parat luoksensa.