Se video av fremstillingen av Korskirken.
Korskirken ble lagt like inn fra den opprinnelige strandlinjen i Vågsbunnen, på et nes som stakk ut i sjøen. Fordi de mange utfyllingene har flyttet sjøkanten utover, ligger kirken i dag et stykke inn i Vågsbunnen. Korskirken ble trolig bygget som sognekirke for søndre del av byen, og i 1320 stadfester biskop Audfinn at hele Stranden sør for Vågen skulle sogne til kirken. Etter at Lille Kristkirke ble revet på kongsgården på Holmen i 1530, fungerte Korskirken også som sognekirke for lensherren og garnisonen på Bergenhus.
I middelalderen framsto kirken relativt lang og smal, og strakte seg nesten 40 meter i lengden (39 x 12 meter, utvendig målt). Murveggen var 1,4-1,5 m tykke, slik at bygningen innvendig var fire ganger så lang som den var bred. Veggene ble murt opp av bruddstein med utvendig kvaderkledning. Kvadermurverk er bare bevart i mindre deler av dagens kirke. I den nederste delen er steinene opptil 150 cm lange.
Både bygningsteknisk og arkitektonisk har Korskirken fellestrekk med både den gjenværende tårnfoten i Nonneseters klosterkirke og Mariakirken, og er trolig et produkt av samme bygghytte. Både Nonneseters klosterkirke, Korskirken og Mariakirken har hatt såkalt rhinsk-lombardiske forbilder med paralleller i domkirken i Lund. De karakteristiske blindbuefrisene er fremdeles synlige under takutspringet flere steder, og to av hjørnepilastrene er bevart i full høyde. En profilert sokkel har gått rundt hele kirken, men er ikke synlig i dag. Korskirken ble fullført mens den klassiserende stilen ennå var enerådende, og er derfor eldre enn Mariakirken. Den østlige delen av kirken er bygget med den karakteristiske klebersteinen fra Urda på Bømlo.
Blindbuefrisene fra midten av 1100-tallet er fremdeles synlige under takutspringet flere steder (Foto: Øystein J. Jansen)
Korskirken hadde trolig en portal i vest. Det er også sannsynlig at kirken hadde en portal i sør (eller nord), men den senere utbyggingen av korsarmer har fjernet alle eventuelle spor. Kirkens opprinnelige vinduer er heller ikke bevart, men det finnes spor av tre middelalderske vinduer i nordmuren. I høy- eller senmiddelalderen ble det bygget et sakristi på sørsiden av kirken, og dagens åpning til sakristiet på korets sørside kan stamme fra middelalderen, selv om den er kraftig omarbeidet i moderne tid.
Dagens kirke har gjennomgått store endringer siden middelalderen. Her er kirken sett fra øst. Vesttårnet i bakgrunnen og korsarmen mot sør til venstre i bildet, var ikke en del av kirken i middelalderen. Vesttårnet ble oppført i 1594 og dagens korsarmer på nord og sørsiden av kirken er bygget på 1600-tallet (Foto: Wikimedia Commons)
Innvendig utgjorde koret trolig rundt en tredjedel av kirkens lengde. I det nordøstre hjørnet er det en rundbuet nisje som kan være et opprinnelig repositorium, et skap til oppbevaring av alterutstyr. Hovedalteret har enten stått inntil eller like foran østveggen. I tillegg til hovedalteret nevner kilder også et Mariaalter (i 1504), et Thorlaksalter (i 1330) og et alter til de 10 000 riddere.
Hvordan bebyggelsen i området ved Korskirken så ut i middelalderen, er noe usikkert. Her dannet tre bekker fra Fløyfjellet et delta som ble kalt Eyrar. Det er mulig at det i første halvdel av 1300-tallet gikk en gate i vinkel eller bue rundt Korskirkeflaten, omtrent der som dagens Hollendergate går, med gårder bygd ut i sjøen foran. Fra 1300-talet kjenner man til åtte gårder som kan ha ligget langs Sutarestretet, dvs. dagens Kong Oscarsgt, og det kan også ha vært flere bygninger på strandflaten nord og vest for Korskirken. Ellers holdt også småhandlere og håndverkere til i Sutarestretet, der det ble solgt fra boder. Et steinkast nord for Korskirken lå Hallvardskirken, og på sør-vestsiden lå Mikaelskirken.
Korskirken ble skadet av brann minst syv ganger fra 1198 til 1702, og alle restaureringene har ført til at kirken er preget av mange stilarter. Korsarmene i sør og nord som karakteriserer kirken i dag, ble bygget først på 1600-tallet. Dagens tårn ble oppmurt 1594, og fikk sin nåværende form i 1720-årene. I 1732 ble kirken kalket overalt utvendig og hvittet innvendig. Dette har man fortsatt med frem til i dag. Det er usikkert om den fint tilhugde kvaderkledningen fra 1100-tallet opprinnelig ble kalket utvendig, men kalkede murer dominerte fra 1200-tallet og utover og dette var nok etter hvert også tilfellet for Korskirken.
Kirken ble restaurert av arkitekt Schak Bull i 1896.