Kostel svatého Mikuláše byl postaven v období baroka mezi lety 1732–1737 stavitelem Kiliánem Ignácem Dientzenhoferem na místě vyhořelého románského kostela.
Interiér chrámu zdobí nástropní fresky zobrazující životy světců sv. Mikuláše, sv. Benedikta a motivy ze Starého zákona. Vytvořil je bavorský malíř Kosmas Damián Assam. Hlavní oltář byl vyroben z umělého mramoru. Za císaře Josefa II. roku 1787 byl kostel zrušen a sloužil různým účelům, mimo jiné též provazochodeckým exhibicím, které se konaly v jeho kupoli.
Kopule mezi věžemi měří 46, 5 m, obě věže jsou o jeden metr vyšší. Zpočátku se mohlo po schodišti vystoupat pouze do jedné z věží. Druhá s ní byla spojena dřevěnou lávkou na vnějšku průčelí. Ta neměla zábradlí a její přechod byl kaskadérským kouskem. Však zde také v roce 1791 vystavoval francouzský vzduchoplavec a přemožitel kanálu La Manche Jean-Pierre Blanchard vzduchoplaveckou techniku. Nové schodiště do druhé věže bylo vsazeno teprve roku 1904.
V roce 1871 byl kostel dán do užívání ruské pravoslavné církvi. V té době daroval ruský car Mikuláš II. kostelu obrovský lustr ve tvaru carské koruny, který byl vyroben v Harrachovských sklárnách. Pravoslavné církvi kostel sloužil až do roku 1914, poté byl využíván jako posádkový kostel či skladiště. Během I. světové války nechal tehdejší velitel pražské posádky znovu obnovit výzdobu kostela vojáky – umělci, kteří by jinak museli na frontu. Až do roku 1901 odděloval kostel od Staroměstského náměstí dvoupatrový Krenovský dům. Ten byl zbořen v rámci asanace a tím se otevřel výhled na chrámové průčelí. Po vzniku Pařížské třídy bylo východní nároží kostela doplněno roku 1906 o sochou sv. Mikuláše a klasicistní kašnu s delfíny. Od roku 1920 kostel užívá Církev československá husitská. Objekt je veřejnosti přístupný, konají se zde koncerty vážné hudby.