Pyhälle Olaville omistettua linnaa rakennettiin paikallisen karjalaisväestön yrittäessä sitä kaikin keinoin estää. Rakennustyömaa oli suojattava puuvarustuksin ja kiviä kuljettaneisiin jolliin oli asetettava haarniskoidut saattojoukot. Novgorodilla ei ollut voimavaroja antaa alaisilleen muuta kuin myötätuntoa, joten alue jo sinne siirtyneine hämäläisineen siirtyi ruotsalaisten valvontaan. Linna rakennettiin vanhojen päälinnojen jälkeen, joten sen nimeksi jäi käyttöön puhekielinen ”Uusilinna”.

Saaren korkeimmalle kohdalle kohosi kolmiomainen päälinna, jonka kussakin kulmassa oli keskenään samankaltaiset korkeat pyöreät tornit. Huipultaan ne olivat sakaraharjaisia ja avoimia. Samalla vauhdilla rakennettiin loputkin saaresta kattava esilinna ja sen molemmissa takanurkissa oli päälinnan kaltaiset korkeat pyöreät sakaraharjatornit. Päälinnan ulkoportti oli suoraan sen seinässä ilman esilinnaa.

Linnan läheisyydessä ei ollut kylää eikä kaupunkia, mutta rannalla linnan kohdalla oli sen rakentamisen ajoilta jäänyt muutaman talon kylä, ns. linnanmalmi. Siinä asui käsityöläisiä ja palvelusväkeä.

Olavinlinnan etuvartioksi rakennettiin jonkin matkaa pohjoiseen kivinen Orivirran saarron linnoitus, joka katkaisi vesireitin Orivedeltä Haukivedelle. Näin vihollinen ei päässyt vesitse kiertämään linnan selustaan. Savonrannan Linnosaaressa linnakkeen rauniot ovat yhä löydettävissä osittain tien alla.

Sadun aikaan linnan voutina oli Pietari Niilonpoika Kylliäinen, ruotsiksi Peder Nilsson Kyllein. Kyllein oli saanut Sten Sturelta rälssivapauden laajoihin maa-alueisiin Viipurin pohjoispuolella ja hänellä oli suuri omaisuus myös Turun seudulla. Pietari ei mennyt naimisiin ja perinnönjaosta selviää hänen sukulaisiaan ja omaisuuksiaan:

http://gamma.nic.fi/~wirmaila/muutsuvut/juusteen/PietariKylliainen.html