Ostanki trdnjave Valjala

Po arheoloških najdbah je bilo ozemlje Saaremaa poseljeno vsaj od 5000 pr. n. št.[1] Na polotoku Sõrve so iz skandinavske železne dobe našli pokopne ladje datirane v 700–750 n. št.. Sage govorijo o številnih spopadih med otočani in Vikingi. Saaremaa je bila najbogatejše okrožje starodavne Estonije in dom zloglasnih piratov, včasih imenovanih tudi vzhodni Vikingi. Kronika Henrika Livonskega opisuje floto šestnajstih ladij in petsto Osilijcev, ki pustošijo po območju današnje južne Švedske, ki je takrat pripadalo Danski.

Verjetno okoli leta 1000, je Gunnar Hámundarson iz Islandije sodeloval v vikinškem napadu na Eysýslo (sodobna Saaremaa). Tam je dobil svoj slavni atgeir, tako da ga je vzel od človeka po imenu Hallgrímur. Njáls saga pripoveduje naslednje:

Od tod so se držali juga do Danske in od tod vzhoda do Smálönda in zmagali, kamor koli so šli. Jeseni se niso vrnili. Naslednje poletje so se držali Rafale (sodobni Talin) in se tam spopadli z morskimi potepuhi, se borili in zmagali. Potem so se usmerili proti vzhodu do Eysýsle (Saaremaa) in tam nekaj časa ležali na rtu. Tam so zagledali moškega, ki se je spuščal iz rta nad njimi; Gunnar je šel na obalo, da bi se srečal z moškim in se pogovoril. Gunnar ga je vprašal, kako mu je ime, in rekel je, da je to Tófi. Gunnar je spet vprašal, kaj hoče. »Tebe želim videti«, reče moški. »Dve vojaški ladji ležita na drugi strani pod rtom in povem vam, kdo jim poveljuje: dva brata sta kapitana - eden se imenuje Hallgrímur, drugi pa Kolskeggur. Vem, da sta mogočna vojaka; in vem, tudi, da imajo tako dobro orožje, da podobnega ne bi smeli imeti. Hallgrímur ima atgeir, ki ga je naredil s kipečimi uroki; in to je tisto, kar govorijo v urokih, da mu nobeno orožje ne bo dalo smrtnega udarca, razen tistega atgeira Tudi to sledi temu, da je takoj znano, kdaj naj bi človeka pobili s tem atgeirom, kajti v njem nekaj poje tako glasno, da se lahko sliši daleč stran - tako močna narava ima v sebi tega atgeira.« 

Kronika Henrika Livonskega opisuje floto šestnajstih ladij in petsto piratov iz Saaremae, ki so pustošili po območju današnje južne Švedske, ki je takrat pripadalo Danski. XIV. Knjiga Geste Danorum, Saxo Grammaticus, opisuje poznejšo bitko na Ölandu leta 1170, v kateri je danski kralj Valdemar I. mobiliziral svojo celotno floto, da bi zajezil vdor piratov iz Couronia (Kurlandija) in Saaremaa.

Morda najbolj znani napad prebivalcev Saaremae se je zgodil leta 1187 z napadom na švedsko mesto Sigtuna (drugi kandidati kot napadalci so Kareli in Kurlandci). Med žrtvami tega napada je bil švedski nadškof Johannes. Arheološka izkopavanja niso potrdila tradicije uničenja mesta. Običajno življenje v Sigtuni se je nadaljevalo, dokler mesto v 13. stoletju ni začelo počasi izgubljati pomena zaradi težav s plovbo, ki jih je povzročil post-glacialni odboj.[2]

Leta 1227 so Saaremaa osvojili Livonski bratje meča med livonskim križarskim pohodom, vendar je odpor lokalnih prebivalcev ostal močan. Križarji so tam ustanovili škofijo Ösel-Wiek. Ko je litovska vojska leta 1236 v bitki pri Sauleju premagala red, so se otočani Saaremaa uprli. Konflikt se je končal s pogodbo, ki so jo podpisali Osilijci in mojster reda. V naslednjem letu so bili bratje meča prevzeti v Tevtonski viteški red. Ko se je križarsko okrožje Saaremae okrepilo, se je tudi krščanstvo bolj uveljavilo na otoku in Saaremaa ima do danes edinstven nabor srednjeveških cerkva v krajih Kaarma, Karja, Kihelkonna, Muhu, Pöide, Püha in Valjala. Križarska trdnjava Grad Kuressaare, v nemščini znan kot Schloss Arensburg, je Tevtonski red zgradil za škofe Ösel-Wiecka (estonsko Saare-Lääne). Gradnja se je začela leta 1380 in je eden najbolj ohranjenih srednjeveških gradov v Estoniji, ki priča o pozni srednjeveški dobi.

V 14. do 16. stoletju in morda prej so se lokalni prebivalci začeli širiti čez Baltsko morje v okoliška območja in tako ustanavljati vasi na livonski obali.

Večino Saaremaa je neposredno upravljala škofija Ösel-Wiek, nekateri deli pa so bili prepuščeni Livonskemu redu. Leta 1559 so škofijo in Saaremaa prodali Danski in sta postali del danske Estonije. Od leta 1570 do 1645 je bil celoten otok v danski lasti.

Leta 1645 je bil Saaremaa z Brömsebro pogodbo odstopljena od Danske na Švedsko. Leta 1721 je bila Saaremaa (takrat znana po švedskem imenu Ösel) skupaj s preostalo Livonijo z Nistadsko pogodbo prepuščena Ruskemu imperiju in postala del Livonskega guvernorata.

Leta 1840 so se v Kuressaareju (takrat znanem kot Arensburg) odprle prve terme, mesto je doživelo renesanso in postalo letovišče za Ruse in baltske Nemce.

V prvi svetovni vojni je estonske otoke oktobra 1917 osvojila cesarska nemška vojska in ostali so okupirani (operacija Albion) do konca sovražnosti. Estonija je postala neodvisna 24. februarja 1918 po oktobrski revoluciji in propadu Ruskega imperija. Kot rezultat pakta Molotov – Ribbentrop je bila nova država junija 1940 vključena v Sovjetsko zvezo kot Estonska sovjetska socialistična republika. Večina baltsko nemškega prebivalstva otoka je bila po Paktu evakuirana v Nemčijo. Otok je leta 1941 zasedla nacistična Nemčija (operacija Beowulf); Nemške čete so tam ostale, dokler jih Rdeča armada v operaciji izkrcanja Moonzunda oktobra in novembra 1944 ni izgnala. Leta 1946 je bila Saaremaa razglašena za območje z omejitvami, zaprto za tujce in večino Estoncev iz celine. Omejeno območje je ostalo do leta 1989.

Estonija je ponovno postala neodvisna 20. avgusta 1991 med razpadom Sovjetske zveze.