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.
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.