Původně stála na dnešním Vršovickém náměstí románská kaple, zasvěcená v roce 1028 Maří Magdaleně. Jméno Sv. Mikuláše nese tento kostel od gotické přestavby a rozšíření v roce 1374. V roce 1704 byl kostel rekonstruován v barokním slohu a v roce 1894 byla chrámová loď prodloužena v neobarokním stylu a byl opatřen novým průčelím. Změnil se i interiér, v němž byly instalovány nové varhany. Naposledy byl kostel sv. Mikuláše rekonstruován v roce 1973. Ve věži jsou dva zvony a to z r. 1511 (od mistra Bartoloměje) a z r.1671 s českým nápisem od zvonaře Mikuláše Löva. U kostela stojí socha svatého Jana Nepomuckého z roku 1725.
Kostel sv.Mikuláše na dnešním Vršovickém náměstí sloužil po staletí místním obyvatelům jako jediný kostel v obci. Koncem 19.století přestal vyhovovat svou kapacitou rychle rostoucímu počtu obyvatel. Proto byla jeho loď r.1896 prodloužena a v r.1902 započaly snahy o postavení velkého kostela. Stavbu nového kostela sv. Václava na náměstí S.Čecha se podařilo realizovat v letech 1929–30.
Nejstarší písemná zmínka o kostele sv.Mikuláše pochází z r.1328. Za jeho předchůdkyni bývala ve starší literatuře považována kaple sv.Marie Magdaleny, zmiňovaná r.1130. Ta byla ale pravděpodobně totožná s kostelem neznámého zasvěcení v Psárech v blízkosti Vyšehradu, který i se vsí zaniknul za husitských válek. Původně gotický kostel sv. Mikuláše byl později několikrát přestavěn a také jeho vybavení a výzdoba se mnohokrát změnily. Ve věži se nachází jeden z nejstarších pražských zvonů. Byl odlit r.1511 a nese jméno sv.apoštola Petra. Interiér je zařízen velmi prostě. Vévodí mu titulní obraz sv.Mikuláše, který v r.2001 vytvořil Miroslav Rada. Varhany postavil v r.1896 Em.Š.Petr jako svůj opus č.90.