I Sverressaga finner vi den første omtalen av Korskirken, i forbindelse med hendelser som fant sted i Bergen i 1181. Ut fra sammenhengen synes det som om kirken da var ferdig og i bruk. Undersøkelser av bygningen har vist at den opprinnelig var en langkirke i romansk stil uten murt tårn. De to tårnene den er avbildet med på Scholeusstikket fra ca. 1580 var derfor trolig bygget i tre. Kort tid etter, i 1594, fikk den et grunnmurt tårn. I 1615 ble det bygget en ny fløy på kirkens sørside, og etter at nordfløyen ble oppført i 1623 har kirken hatt den korsformen vi kjenner i dag.

Kirken ble rammet av bybrannene i 1198, 1248, 1413, 1476, 1582, 1640 og 1702. De mange restaureringene den har vært gjennom har satt sitt preg på bygningen, som i dag har flere stilarter. Langskipet ble bygget i romansk stil, men vi ser også elementer av gotisk stil. Tårnet ble oppført under renessansen, mens fløyene tilhører barokkens tidsalder. I forbindelse med restaureringsarbeider på 1800-tallet og senere fikk kirken sine nåværende vinduer med sprosseverk i støpejern. Korskirkens vakre kirkeklokker ble laget i Amsterdam tidlig på 1700-tallet. Orgelet fra 1890-årene ble bygget av den kjente tyske orgelmakeren Albert Hollenbach, men har senere blitt utvidet og reparert. Takstoler, prekestol og kirkebenker er også fra 1890-årene.

Kirken ble rammet av bybrannene i 1198, 1248, 1413, 1476, 1582, 1640 og 1702.

Etter at kirkene på Holmen ble revet rundt 1530, synes Korskirken å ha tjent som sognekirke for sivile og militære på Bergenhus. Fra 1600-tallet til etter andre verdenskrig har den vært garnisonskirke. I koret er det reist et minnesmerke over soldatene som falt ved Alvøen 16. mai 1808, i kamp mot en engelsk fregatt.

Av kirkegården står der bare igjen en liten parsell med et par graver. En gravhelle er tatt inn i kirken og plassert på nordveggen til prestesakrestiet. Den ble reist til minne om Alida Fischer, født Brun, datter til biskop Johan Nordahl Brun. Hun giftet seg med skolestyrer Johan A. Fischer og ble mor til en liten gutt, før hun døde 16 år gammel i 1801. På hennes minnestein står det:

Her gjemmes en tidlig udsprungen fuldmoden, men hastig visned Rose, Alida Fisher f. Brun den 5/2 – 1785 død 10/5 – 1801. Elsked Hustro for Joh. Ad. Fisher. Kjer datter af og glad Moder til en Johan Nordahl. Hun sneg seg let og rask bag om alle Sorger, gjennem Livets korte men bedste glæder ned under denne steen. På den lod Manden indhugge Naturens Skjønneste Ord Min Første Kjærlighet.