Kirken blev bygget i 1200-tallet og var dengang den ene af København tre kirker.
Den var især handelsmændenes og søfolkenes kirke. Søfolkene kom her, inden de skulle ud at sejle, og kirken var indviet til de søfarendes helgen, Sankt Nikolaj.
Nikolaj var også helgen for fiskere, bagere, apoteker og jurister – og børn. Kirken blev dog også brugt af borgere i almindelighed.
Kirken var den næststørste – og næstrigest udsmykkede – efter Vor Frue Kirke, og var rig på indtægter, f.eks. fra boder i Dragør og en gård på Amagertorv, som var herberg for tyske købmænd.
I begyndelsen af 1500-tallet blev kirken af ukendt årsager revet ned og genopført, så den lignede Vor Frue Kirke, men uden tårn. Et tårn fik den dog igen omkring 1664, hvor bygmesteren Albertus Mathiensen (- 1668) udførte et etagetårn med spir, der var forsynet med kugler og andet pynt..
I 1529 blev Hans Tavsen præst ved kirken, og kirken blev i de følgende år midtpunkt for reformationens udbredelse i hovedstaden. Her holdt han den første gudstjeneste på dansk.
Efter reformationen blev kirken i højere grad kirke for borgerskabet og adelen. Peder Griffenfeldt havde sin egen stol i kirken, og fremtrædende personer, som Hans Egede og Jens Munk er begravet her.
Næsten alt inventar gik tabt under den store brand i 1795. Skibet og kirkespiret brændte, så kun tårnet stod tilbage. I dag kan man i den nederste del af tårnet se toppen af spiret, som styrtede ned ved branden.
Efter branden i 1795 blev Sankt Nikolaj ikke længere brugt som kirke, og har siden været brugt til andre formål. Tårnet blev siden brugt som udkigstårn for vægterne, som i tilfælde af ildebrand skulle holde en lanterne ud i strakt arm i den retning ildebranden var.
Fra toppen flagede man i 1844, da Bertel Thorvaldsen vendte hjem til Danmark, som signal til københavnerne om, at de skulle tage til Københavns Toldbod og modtage ham.
Tårnet blev også brugt til det tidssignal, der i form af en kugle på en stang, hver dag kl. 13 markerede den nøjagtige tid.
Nikolaj Tårn blev én af byens attraktioner, som man gerne viste frem. Det manglede dog sit gamle spir, men det fik den i 1909, da brygger Carl Jacobsen bekostede opsætningen af et nyt
Frem til 1957 rummede bygningen Københavns Hovedbibliotek. I dag fungerer den om udstillingsstedet Kunsthallen Nikolaj.
I det nordøstlige hjørnet af kirken er der i muren indsat en mindetavle for præsten Hans Egede og hans hustru Gertrud Rasch. Parrets lå begravet på den nu nedlagte kirkegård ved Sankt Nikolaj Kirke. Mindetavlen er opsat i 1921.
I kirkemuren sidder også en skulptur, der forestiller maleren og filosoffen Svend Aage Tauscher ( -1982). Figuren er udført af Troels Lybecker og opsat i 1987.
