Belegt ist, dass die Insel Munkholmen bereits vor dem 12.Jahrhundert den Herrschern von Trondheim als Hinrichtungsstätte gedient hat. In den Aufzeichnungen des altisländischen Dichters und Historikers Snorri Sturluson wurde Munkholmen unter dem Namen „Nidarholm“ erwähnt. Von ca. 1100 bis zur Reformation 1537 befand sich hier das Benediktiner-Kloster „Nidarhom“. Die Benediktiner waren sehr mächtig, hatten große Besitztümer und Ländereien auf dem Festland. Mit eigenen Schiffen betrieben sie sogar selbstständigen Handel mit England.
Das Kloster fiel insgesamt drei Großbränden zum Opfer : 1210, 1317 und kurz vor der Reformation 1531. Es war die letzte katholische Hochburg in Norwegen. Im Zuge der Reformation allerdings mussten die Mönche und der Erzbischof von Trondheim fliehen. Das Kloster verfiel und die Insel wurde als Viehweide genutzt. Erst Mitte des 17. Jahrhunderts wurden die Reste des Klosters entfernt und die Insel befestigt. In dieser Zeit erhielt sie auch ihren jetzigen Namen „Munkholmen“.
Während zweier Kriege zwischen 1657 und 1660 wurde die Insel von den Schweden besetzt und mit einer Kanonenbatterie bestückt. Die dänisch-norwegische Union eroberte 1660 Trøndelag und damit auch Munkholmen zurück und begann mit einem endgültigen Ausbau der Insel zur Festung. Zunächst gab es nur eine einfache Verteidungsmauer und die Wohnung des Kommandanten bestand aus Holz. Dazu stellte man 18 Kanonen auf. In den folgenden Jahrzehnten nahm die Festung jedoch immer mehr Gestalt an. Zunächst wurde der große Zentralturm gebaut und der innere Turm fertiggestellt. Da die Anlage von Beginn an auch als Staatsgefängnis geplant war, richtete man im Turm auch Aufenthaltsräume ein. Zwischen 1680 und 1690 erhielt die Anlage ihre sternförmige Gestalt. 35 Kanonen wurden installiert und eine neue Kommandantenwohnung gebaut. Am 26.August 1690 wurde Munkholmen offiziell eingeweiht. Doch auch danach baute man die Festung bis 1707 weiter aus. Erst dann erhielt sie ihr vorläufiges Aussehen als Sternfestung.
Als Staatsgefängnis wurde Munkholmen von 1680 - 1850 genutzt. Während der Napoleonischen Kriege 1792 - 1815 erwies sich die Bauweise der Festung allerdings als nicht zweckmäßig. Erneut wurde die Anlage umgestaltet, nun vieleckig. Bei der Fertigstellung war die Festung von 8-10 m starken Mauern umgeben, hatte 60 Kanonen und Raum für 500 Soldaten. Für die Munitionslagerung wurden u.a. im großen Zentralturm die Gefängniszellen entfernt.
Munkholmen galt als eine der stärksten Festungen Skandinaviens, erlebte jedoch keine Kampfhandlungen. Während des 2.Weltkrieges errichteten die deutschen Besatzer auf der Insel eine Verteidigungsanlage mit 6 Flakstellungen zum Schutz der U-Boot-Basis in Trondheim. Restliche Betonfundamente sind noch heute sichtbar.
Heute ist Munkholmen ein beliebtes Ausflugsziel für Trondheimer und Touristen. Im Sommer besteht regelmäßiger Fährverkehr. Für Interessierte werden auch Führungen angeboten.