The oldest part of Korskirken belongs to a Romanesque long church as old as Mariakirken. The first time we hear of it is in 1181. Evidently this is when it was finished. The construction with squared stones and remains of a blind arch freeze below the ceiling cornice provides evidence that it was built by the same craftsmen who built Mariakirken. In the 1590s a western steeple was added, and in 1615 the southern chancel wing was built. The northern chancel wing was built in 1632. The portal is a major monument within Norwegian Renaissance. Remains of a corresponding portal stand in the southern chancel wing.
The church was given its present helmet and spire following the town fire in 1702. In 1896 the architect Schak Bull inserted Romanesque arches in the chancel and steeple base, on the model of the side nave portal of Stavanger cathedral, and replaced the church’s vault with an elegant open roof truss construction.