Gadens navn er forbundet med Sankt Nikolaj Kirke, som var én af de første kirker i København.
Nikolaj var helgen for bl.a. søfolk, og Nikolajgade går gennem det kvartér, hvor mange af byens søfolk boede.
Navnet er dog forholdsvis nyt, for gaden erstattede i 1894 en ældre smøge, der blev kaldt Skvaldergaden.
Gadens nordligste del mellem Nikolaj Plads og Østergade hed tidligere Halmstræde.
![](https://www.hovedstadshistorie.dk/wp-content/uploads/2023/12/Nikolajgade-22-1-RED.jpg)
Ejendommen på hjørnet af Dybensgade er den såkaldte Halds Gård (herover), som blev opført i 1799 for en bagermester.
I Nikolajgade lå fra 1825 et sømandshjem, der var stiftet af Peder Norden Sølling. Midlerne til hjemmet kom fra indsamlinger, der bl.a. foregik ved at man kunne lægge bidrag i en pengebøsse, der var indrettet i en gammel bombe. Hjemmet fik derfor navnet “Bombebøssen”. Stiftelsen flyttede i 1891 til Overgaden Oven Vandet.