Jest to ulica wychodząca z zachodniego narożnika Rynku Starego Miasta do zbiegu ulic Freta, Długiej i Mostowej. Wytyczona została przy lokacji miasta Warszawy już na przełomie XIII i XIV w. Wyjazd z miasta prowadził wtedy przez gotycką Bramę Nowomiejską rozbudowaną w XIV i XV w., a w pierwszej połowie następnego stulecia wzmocnioną barbakanem.
W XIV w. stanęły przy niej drewniane zabudowania kościoła i szpitala św. Ducha oraz łaźnia miejska. Dopiero w XVI w. powstała zwarta, murowana zabudowa zamieszkała przez patrycjat miejski. Tak jak w przypadku innych ulic Starego Miasta, pożar w 1607 r. strawił także zabudowę Nowomiejskiej. Kolejne zniszczenia przyniosły walki ze Szwedami o Bramę Nowomiejską w 1656 r. Zrujnowany został wówczas odcinek ulicy poza murami: kościół, szpital, łaźnia i domy mieszkalne, a sama brama poważnie uszkodzona. Odbudowę kościoła, szpitala i klasztoru przy rogu Nowomiejskiej i Podwala przeprowadził zakon Paulinów.
W XVIII w. na miejscu zasypanej fosy wzniesiono kamienice mieszkalne, zaś nowomiejskie bramy zostały wchłonięte przez budowle kancelarii rosyjskiej i wójtowskiej Starej Warszawy, a także kramy i składy towarów kupców gdańskich (tzw. Gdańska Piwnica) oraz domy mieszkalne.
W XVII i XVIII w. Nowomiejska należała do najważniejszych ulic Starej Warszawy zamieszkałych przez patrycjat miejski: Fukierów, Gizów, Dzianotów i Drewnów. W końcu XVIII w. mieszkał przy niej słynny prezydent Warszawy – Jan Dekert. Na początku XIX w. przy Nowomiejskiej urządzono targowisko, po czym po dwudziestu latach je zamknięto.
W XIX w. ulicę zwano też Gołębią. Pod koniec wieku odkryto fragmenty murów i barbakanu. W latach 1937-38 (pod przewodnictwem Jana Zachwatowicza) część z nich zrekonstruowano i odsłonięto wraz z dawnym mostem nad fosą, rozbierając domy mieszkalne i jatki po stronie nieparzystej.
W 1944 r. zabudowa ulicy została prawie całkowicie zniszczona. Ocalały tylko mury obronne i fragmenty ścian parterowych. W latach 50. XX w. kamienice odbudowano, przywracając im piękne elewacje. Barbakan zrekonstruowano w gotyckiej cegle do pierwotnej wysokości, uwidoczniono fundamenty Bramy Nowomiejskiej.