Ulica Nowolipki powstała po 1624 roku jako dawna droga narolna, wytyczona na gruntach posiadłości brygidek zwanej Nowe Lipie. Biegła od ulicy Nalewki w kierunku zachodnim. Początkowo była bardzo słabo zabudowana – jeszcze w 1762 roku drewniane budynki znajdowały się tylko w początkowym jej odcinku. Dalej dominowały ogrody, co dało początek nieoficjalnej nazwie „Ogrodniki”.
Obecną nazwę „Nowolipki” zatwierdzono w 1770 roku, choć przez pewien czas funkcjonowała także forma „Nowolipska”. W tym samym roku, z inicjatywy geometry Macieja Deutscha, ulica została uregulowana i przedłużona do ulicy Wolność.
Od 1770 roku przy skrzyżowaniu z ulicą Nalewki istniał magazyn karowy – remiza dla wozów wywożących nieczystości, zaprojektowana przez Stanisława Zawadzkiego lub Jakuba Fontanę. W 1775 roku, na sąsiedniej działce, rozbudowano pałac Konstancji Hilzenowej, żony wojewody mińskiego Jana Augusta Hylzena. Po 1784 roku pod numerem 7 wzniesiono pałacyk Jana Poltza, który przed 1792 rokiem stał się własnością Stanisława Sołtyka.
W epoce Królestwa Kongresowego reprezentacyjny charakter uzyskał początkowy odcinek ulicy. Magazyn karowy przekształcono w koszary Gwardii Artylerii Koronnej, a pałac Hilzenów po 1795 roku przejął Tadeusz Mostowski, minister spraw wewnętrznych Księstwa Warszawskiego. W 1824 roku Antonio Corazzi przebudował pałac Mostowskich na siedzibę Komisji Rządzącej Spraw Wewnętrznych i Duchownych.
Na posesji nr 33 już przed 1819 rokiem istniała pierwsza w Warszawie gisernia wosku Karola Schultza. W 1835 roku IV Oddział Straży Ogniowej zajął teren dawnego magazynu karowego, gdzie powstała również wieża telegraficzna.
W latach 1840–1843 pod numerem 11/15 wzniesiono gmach II Gimnazjum Męskiego, w którym tymczasowo mieścił się Instytut Szlachecki. W tym budynku mieszkała w dzieciństwie Maria Skłodowska-Curie. Rodzina Skłodowskich wyprowadziła się stąd w 1873 roku.
Pałacyk Sołtyka, wcześniej siedziba Dyrekcji Ubezpieczeń, w 1843 roku mieścił pierwszą w mieście stałą Kasę Ubezpieczeń i Oszczędności. Po 1864 roku urządzono tam meczet, a przed 1868 rokiem drukarnię Józefa Ungra, wydawcę „Tygodnika Ilustrowanego” i „Wędrowca”.
Po 1840 roku inwestycje zamarły na 25 lat. Około 1860 pojawiło się oświetlenie gazowe, a w 1863 przedłużono ul. Karmelicką. Lata 1875–1888 to okres chaotycznej zabudowy spekulacyjnej, jednak niektóre kamienice miały już wyższy standard architektoniczny.
Nowolipki zyskały kilka charakterystycznych budynków, m.in. neogotycką kamienicę Eugeniusza Torzewskiego (nr 51) z czerwoną cegłą i wieżyczką. Podobny styl miały kamienice nr 41 i 43. W latach 1892–1896 powstał kościół św. Augustyna z 70-metrową wieżą.
Około 1911 roku wybudowano nowoczesną kamienicę dla Karola Piltza. Do 1939 roku przy ulicy działało wiele zakładów produkcyjnych, m.in. fabryka kas, garbarnia, wytwórnia rowerów.
W 1914 roku do kamienicy nr 53 wprowadził się Józef Rotblat, późniejszy laureat Pokojowej Nagrody Nobla (od 2018 jego imieniem nazwano pobliski skwer). W okresie międzywojennym mieścił się tam III komisariat Policji Państwowej. W kamienicy pod nr 7 znajdowała się redakcja „Naszego Przeglądu” i dziecięcego „Małego Przeglądu” założonego przez Janusza Korczaka.
W 1939 roku zniszczono budynek szkoły nr 11 i skrzydła pałacu Mostowskich. W listopadzie 1940 roku Nowolipki zostały włączone do warszawskiego getta. Po akcji deportacyjnej w 1942 roku końcowy odcinek wyłączono z jego granic. W czasie powstania w getcie niemieckie wojska zniszczyły większość zabudowy. Przetrwał jedynie kościół św. Augustyna.
W piwnicach szkoły Bera Borochowa (nr 68) ukryto części Archiwum Ringelbluma – w sierpniu 1942 i lutym 1943 roku.
Powstanie warszawskie w 1944 roku przyniosło dalsze zniszczenia – spłonęły m.in. koszary Straży Ogniowej oraz pałac Mostowskich.
Po wojnie ulicę skrócono do ul. Przejazd (ob. gen. Władysława Andersa), usunięto brukowaną nawierzchnię. Pod numerem 20 zachowały się oficyny dawnej kamienicy Warszawskiej Gminy Żydowskiej.
Nowe osiedle Muranów wybudowano bezpośrednio na gruzach. Niektóre budynki stoją na pagórkach utworzonych z przysypanych ruin.
W 2021 roku na skwerze między blokami nr 28 i 30 odsłonięto upamiętnienie w miejscu odnalezienia pierwszej części Archiwum Ringelbluma, zaprojektowane przez Łukasza Mieszkowskiego i Marcina Urbanka.