Korskirken is first mentioned in king Sverre’s Saga in 1181. According to the saga, the church seemed to be ready built and in use at the time.
Apparently the church was originally a long church with wooden towers, constructed in a Romanesque style. The stone tower was not built until 1594. The south wing of the church was built in 1615, and the north wing was raised in 1623 giving the church its shape as a cross.

The church has burnt in big town fires in 1198, 1248, 1413, 1582, 1640 and 1702. All the reconstructions have left the church a conglomerate of different styles. We recognize the original Romanesque style in the nave, which is mixed with a hint of Gothic style. The tower was built during the Renaissance, while the wings are Baroque.

The church bells were made in Amsterdam in the early 18th century, while the organ was constructed by German Albert Hollenbach in the 1890s. The pulpit also originates from this period.

After the deconstruction of the cathedral at Holmen around 1530, Korskirken may have become the parish church for both civilian and military use at Bergenhus Fort and Castle. The garrison at Bergenhus Fort and Castle has belonged to the church up until the Second World War.

All that is left of the churchyard is a small patch with a few graves. One gravestone has later been mounted on the northern wall of the sacristy. It was originally raised in memory of Alida Fisher, the daughter of one of Bergen’s most renowned bishops, Johan Nordahl Brun.

Alida married schoolmaster Johan A. Fisher, and became mother to a little boy before she died 16 years old in 1801. On her gravestone is carved:
“Here lies an early sprung, ripe, but hastily withered rose, Alida Fisher nee Brun on 5/2–1785 dead 10/5–1801. Beloved wife of Joh. Ad. Fisher. Loved daughter of and loving mother to a Johan Nordahl. She slipped easily and quickly past all sorrows, through life’s short but wonderful joys, until she reached below this stone. On it her husband has carved nature’s most beautiful words – My First Love.”