Od czasów reformacji religia katolicka była zakazana w królestwie Norwegii. Dopiero w XIX wieku na mocy królewskiej rezolucji z dnia 6 marca 1843 roku, norwescy katolicy otrzymali pozwolenie na utworzenie pierwszej własnej parafii. Parafia ta powstała w Oslo, noszącym wówczas nazwę Christiania. W 1845 roku prawo to objęło całą Norwegię.
Nasza parafia liczy sobie ponad 19.000 wiernych z ponad 100 krajów świata. Dla porównania w roku powstania kościoła (1876) należało do niego ok. 20 wiernych.
Biskup Jacob Lorenz Studach wysłał pierwszego katolickiego księdza do Bergen. Był nim Norweg Christopher Holfeldt-Hauen. Pierwszą Mszę św. celebrowano na Boże Narodzenie roku 1857. Kaplicą, która służyła za Dom Boży było mieszkanie znajdujące się na Kalmargjerdet.
W roku 1864 ksiadz Holfeldt-Houen zakupil na ówczesnej Christiesgate (dzisiejsza Nygårdsgate) grunt pod budowę kościoła. Kamień węgielny położony został rok później przez budowniczego, a zarazem proboszcza księdza Daniela Stuba, którego symboiczny grob znajduje sie za kościołem.
Budowa kościoła trwała 11 lat. Dnia 29 czerwca 1876 roku w święto św. Piotra i Pawła kościół został konsekrowany i oddany do użytku wiernych. W tym samym roku otwarto również przykościelną szkołę katolicką, która prowadzona była początkowo przez siostry zakonne. W latach osiemdziesiątych szkoła otrzymała nowe lokale w pobliżu kościoła i jest obecnie jedną z najbardziej cenionych szkół w Bergen.
W roku 1896 została wykopana pod kościołem krypta używana wtedy, jak i teraz jako miejsce spotkań. W tym samym też roku ukończono budowę szpitala katolickiego, który znajdował się w dzisiejszym Birgittahjemmet, a później szpital „Florida” – obecnie komunalny dom opieki.
Od 1901 roku aż do upaństwowienia służby zdrowia pracowały w szpitalu siostry św. Franciszka Ksawerego mające swój dom na Marias Minde (Sandviken).
