Riddarholmskyrkan uppfördes ursprungligen som klosterkyrka åt Gråbrödraklostret i Stockholm. Klostret grundades enligt dess bevarade diarium år 1270, men klosterkyrkan påbörjades inte förrän ungefär ett decennium senare. Man vet inte heller när kyrkan stod färdig, men vid 1300-talets ingång var den troligtvis fullbordad. Kyrkan byggdes alltså omkring 1280–1300 med långhus, kor och vapenhus i norr. Den ursprungliga planen var tvåskeppig – en vanlig plan för mendikantordnarnas klosterkyrkor i Skandinavien och norra Tyskland under medeltiden. Klosterkyrkan saknade torn, eftersom franciskanernas ordensregler inte tillät torn på klosterkyrkorna.[1]

Under 1400-talets förra del gjordes klostrets södra korsgång om till sidoskepp genom upptagningar i södra långhusväggen. Före detta hade ett kapell, nuvarande sakristia, uppförts söder om långhusets östligaste travé. Under 1400-talet tillkom även en förhall i väster.

Johan III lät förhöja kyrkans västtorn till ett torn med hög spira, där spiran troligen ritades av Willem Boy. Det första av kyrkans vidbyggda gravkor, det gustavianska gravkoret på korets sydsida, uppfördes 1632–1634 för Gustav II Adolf. Koret ritades av Kristian Blume i holländsk renässansstil. Under de närmast påföljande decennierna tillkom långhusets krans av gravkor. Jean de la Vallées planer för om- eller nybyggnad av kyrkan, samt hans förslag till det Karolinska gravkoret, kom aldrig till utförande. Karolinska gravkoret påbörjades 1675 efter Nicodemus Tessin d.ä.:s ritningar. Endast det underjordiska valvet blev dock färdigt och arbetet fullbordades inte förrän i mitten av 1700-talet, då efter ritningar av Carl Hårleman.

Åren 1811–1817 genomgick kyrkan en genomgripande restaurering under ledning av Fredrik Blom. Därefter flyttades Statens trofésamling till Riddarholmskyrkan vid en högtidlig ceremoni 1817. Fanorna sattes upp i gravkoren och runt pelarna.[2] Den 28 juli 1835 slog blixten ned i Riddarholmskyrkans torn. Därvid uppstod en svårsläckt eldsvåda som varade i tre dagar. Vid Riddarholmskyrkans brand 1835 störtade tornspiran samman och det brann i stentornet liksom i hela övre delen av själva kyrkan. Småtornen stod länge emot, men föll slutligen och klockorna föll ned från sina ställningar. Man lyckades dock hindra elden att komma in i kyrkans inre.[3] Det rapporterades om Riddarholmskyrkans brand 1835 i nyhetsmagasin och om utseendet efter branden. Vid återuppbyggnaden av kyrkan tillkom åren 1838–1841,[2] på initiativ av Samuel Owen,[4] de karaktäristiska gjutjärnsspirorna, gjutna vid Åkers styckebruk. Den nygotiska formen ritades i en första variant av skulptören Erik Gustaf Göthe men omarbetades av Carl Gustaf Blom Carlsson. Föregångare var den pågående restaureringen av Katedralen i Rouen där gjutjärnsspirorna dock kom att bli så ifrågasatta att bygget fick avbrytas.[5] En av de ursprungliga hörntornens spiror från 1830-talet står numera uppställd utanför Tekniska museet i Stockholm. Nuvarande tornspiror togs fram genom en omgjutning vid 1967–1970 års restaurering. Den nuvarande kyrkklockan, Serafimerklockan, göts 1839 efter förlaga av Axel Magnus Fahlcrantz med återanvändande av bronsen från de äldre klockorna som förstördes i branden.[6]

Kyrkan restaurerades 1841–1846 under ledning av stadsarkitekten i Stockholm, Per Axel Nyström den äldre (1793–1868). Efter restaureringen sattes trofésamlingen, den svenska statens samling av militära troféer, upp igen på samma sätt som före branden 1835. Åren 1856–1860 tillkom kyrkans sista tillbyggnad: det Bernadotteska gravkoret, ritat av Fredrik Wilhelm Scholander. Statens trofésamling fanns i Riddarholmskyrkan fram till 1906, då den flyttades och införlivades i Statens trofésamling i Armémuseum. Kyrkan restaurerades igen 1914–1922 under ledning av hovintendenten Gustaf Lindgren. De vetenskapliga undersökningarna av kyrkan leddes av professor Martin Olsson, sedermera riksantikvarie.[2] Medeltida putsytor och golvnivå återställdes vid restaureringen. Slutkostnaden för denna renovering blev 525 000 kronor.[7]