Nikolaikirken var en steinkirke som lå øverst på allmenningen den gav navn til, og ifølge Bergens Fundas var grunnsteinen lagt i Øystein Magnussons regjeringstid og trolig reist i løpet av 1120- og 1130-årene; første gang omtalt i skriftlige kilder 1160, året da Gregorius Dagsson søkte dit under et sammenstøt med Erling Skakke. Kirken var antakelig utsatt for brann 1198 og 1248. Etter byloven av 1276 skulle det holdes vakt fra tårnet og varsles om brann og fiendtlig overfall, og det var klokkene i Nikolaikirken som hver kveld varslet at all ild skulle slukkes rundt om i byen. Kirken ble sannsynligvis skadet eller ødelagt ved bybrannen 1413 og igjen 1476. På Scholeusstikket (ca. 1580) er den fremstilt som ruin, men med dominerende steintårn. Stein fra kirken finnes i kjellermurene i nabolaget, på toppen av Steinkjellerbakken og mellom Øvregaten 17 og Forstandersmuget. Ruinene ble utgravd 1895, og funn som ble gjort, er oppbevart i Historisk museum.

Nikolaikirken føyde seg i høymiddelalderen inn i det typiske kontinentale byinteriøret, med torget nederst på Bryggen, rådhus og vinkjeller på allmenningen og kirken øverst.

Se også oversikt over Bergens middelalderkirker.