L'édifice a été construit en 1856 en style néogothique par les architectes allemands Heinrich Ernst Schirmer(de) et Wilhelm von Hanno dans le faubourg d'Hammersborg qui venait d'être urbanisé. La construction a été financée sur des fonds privés venus de Norvège et de l'étranger. Saint-Olaf devait servir à la communauté catholique d'église paroissiale, alors que la liberté du culte pour les catholiques était rétablie depuis quelques années. La reine Joséphine, qui avait conservé sa foi catholique, fut l'une des principales donatrices. Elle fit également don d'un tableau, copie de la Madone Sixtine, qui se trouve à droite du maître-autel.
L'église est construite en brique, selon la mode néogothique fort appréciée en Suède et en Norvège à l'époque, et sa façade occidentale est surmontée d'un unique clocher surmonté d'une flèche.
La cathédrale est restaurée en 1975-1976 et adaptée aux besoins liturgiques post-conciliaires sous la direction de l'évêque de l'époque, John W. Gran. L'autel, selon les nouvelles normes du rite de PaulVI, est transformé et les colonnes sont rénovées. L'orgue, en style néobaroque, est restauré en 2002.
La cathédrale Saint-Olaf a reçu la visite du pape Jean-PaulII en 1989 qui lui a fait don de reliques de saint Olaf.
Norvège
