
Kuparipiirros Olavinlinnasta 1700-luvun loppupuoliskolta. Pohjoisesta päin kuvatussa kuvassa on näkyvissä vielä kaikki linnan viisi tornia
Olavinlinna päätettiin rakentaa turvaamaan Pähkinäsaaren rauhan rajaa. Linnan rakentaminen aloitettiin vuonna 1475in Eerik Akselinpoika Tott toimesta. Hän palkkasi ulkomaalaiset muurarit ja muurimestarit Tallinnasta. Lähiseudun asukkaat pakotettiin rakennustöihin. Venäläiset häiritsivät rakennustöitä, sillä linnaa rakennettiin Venäjän puolelle. Rakennusalueelle rakennettiin ensin puiset suojavallit, jotta työtä saataisiin tehdä rauhassa. Varsinaisesta linnasta rakennettiin ensin päälinna sekä sen kolme tornia; Kirkkotorni, Kellotorni ja Pyhän Eerikin torni.
Päälinna tärkeimmiltä osiltaan valmistui todennäköisesti vuonna 1483. Tott, joka oli sotilas ja Lagnön ritari, päätti nimetä linnan kaikkien ritareiden suojelijan, Pyhän Olavin, mukaan.
Linnan rakennusmateriaaleina käytettiin puuta ja kiveä. Liuskemainen luonnonkivi saatiin lähiympäristöstä. Tornien lisäksi päälinnaan kuului myös niitä yhdistävään kehämuuriin liittyvät asuinsiivet. Linnan tärkeimmät asuinhuoneet oli sijoitettu torneihin. Itäsiivessä oli komeasti holvattu suuri juhlasali, Kuninkaansali, ja sen alla sijaitsi Linnantupa. Päälinnan kolmesta tornista Pyhän Eerikin torni on raunioitunut, ja nykyään siitä on nähtävissä vain pohjakerroksen rakenteita. Kustaa Vaasan tultua Ruotsin hallitsijaksi, päälinnan kolmea tornia korotettiin ja rakennettiin suuri tykkitorni, Paksu torni. Lisäksi linnan muureja vahvistettiin. Linnaan rakennettiin viides torni, Kijlin torni, 1600-luvun alkupuolella.
Savonlinnan kaupunki alkoi kasvaa linnan rakennustöiden alkamisen jälkeen. Kaupunkioikeudet Savonlinna sai vuonna 1639.
Suuri Pohjan sota Ruotsin ja Venäjän välillä alkoi vuonna 1700. Pitkän piirityksen jälkeen Ruotsi-Suomi menetti linnan ensimmäisen kerran venäläisille vuonna 1714. Venäläiset purkivat pommituksissa pahoin kärsineen Pyhän Eerikin tornin. Ruotsi-Suomi sai linnan takaisin Uudenkaupungin rauhassa vuonna 1721. Se kuitenkin menetti linnan toisen kerran Turun rauhassa Hattujen sodan jälkeen 1743t. Venäläiset aloittivat linnan voimakkaan varustamisen, jonka muistona ovat Olavinlinnalle tyypilliset tornien tiilirakenteiset pyöreäikkunaiset yläosat, sekä länteen osoittavat bastioni. Ruotsalaiset ja suomalaiset piirittivät linnaa vuonna 1788, onnistumatta sitä kuitenkaan valloittaa. Paksu torni tuhoutui ruutivaraston räjähdyksessä 1791.
Kun Suomi siirtyi Suomen sodan jälkeen Venäjän alaisuuteen vuonna 1809, linna menetti sotilaallisen merkityksensä, sillä rajanmuutoksen jälkeen se sijaitsi hyödyttömästi sisämaassa. Linna toimi pelkkänä kasarmina vuoteen 1847 asti ja sen jälkeen muutamia vuosia vankilana ja varastona. Tyhjänä ollessaan sekä vuosina 1868 ja 1869 riehuneissa kahdessa suuressa tulipalossa linnan kunto huononi. Linnan restaurointi aloitettiin 1800-luvun lopulla ja linnasta tehtiin muinaismuistona suojeltu kohde. Viimeisimmät laajamittaiset entistämistyöt aloitettiin vuonna 1961 ja saatiin valmiiksi vuonna 1975. Linna vaatii jatkuvia korjaustoimenpiteitä.
Nykyisin linna on suosittu, ympäri vuoden auki oleva turistikohde. Olavinlinnan suurella linnanpihalla järjestetään jokakesäiset Savonlinnan Oopperajuhlat. Linnassa järjestetään myös näyttelyitä. Linnan huoneita voi vuokrata myös yksityistilaisuuksia varten.
