Najzgodnejši pisni zapis, ki omenja grad Kuressaare, je iz 1380-ih let, ko je Tevtonski viteški red začel graditi za škofa iz Ösel-Wiecka.[1] Nekateri viri trdijo, da je bil prvi grad zgrajen iz lesa.[2][3] Ko so se prebivalci Saaremaae močno upirali tujim prizadevanjem, da bi jih pokristjanili, je bil grad nedvomno zgrajen kot del širših prizadevanj križarjev, da bi dobili nadzor nad otokom. Že od samega začetka je bila trdnjava škofa Saare-Lääne (nemško Ösel-Wiek) in je ostala ena najpomembnejših gradov škofije do razpada med livonsko vojno.[4]

 

Tloris gradu in obzidja Kuressaare leta 1710

Leta 1559 je Danska-Norveška prevzela nadzor nad Saaremaao in gradom Kuressaare. V tem času so bile utrdbe posodobljene. Po miru v Brömsebru, ki je končal vojno med Švedsko in Dansko-Norveško v letih 1643-1645, je Saaremaa prešel v švedske roke. Švedi so modernizacijo trdnjave nadaljevali do leta 1706. Po veliki severni vojni sta Saaremaa in grad Kuressaare postala del Ruskega imperija.

Ko so se meje Ruskega imperija postopoma pomikale naprej proti zahodu, je Kuressaare izgubil svojo strateško vrednost. Zlasti po finski vojni in tretji delitvi Poljske se je vojaški poudarek premaknil od Estonije. Leta 1836 se je po gradnji trdnjave Bomarsund na Alandu ruska posadka na Kuressaareju umaknila. Dejstvo, da gradu Kuressaare niso zasedle vojske, ki so se borile v Krimski vojni, kaže tudi na njegov izgubljeni strateški pomen.[5] V 19. stoletju so grad uporabljali kot ubožnico.

V letih 1904–12 sta grad obnovila arhitekta Karl Rudolf Hermann Seuberlich in Wilhelm Neumann.

Leta 1941 so grad kot trdnjavo uporabljale okupacijske sovjetske sile, ki so na grajskem dvorišču usmrtile 90 civilistov. Nacistična invazija in okupacija, ki je sledila, je na grajskih tleh ubila več kot 300 ljudi.[6][7][8][9][10]

Leta 1968 je potekala druga obnova, ki jo je tokrat vodil arhitekt Kalvi Aluve.[11]

Danes je v gradu muzej Saaremaa.