Początki ulicy Koźlej sięgają XVI wieku, kiedy była traktem prowadzącym do Zakroczymia. W 1621 roku jej długość skrócił usypany Wał Zygmuntowski. Dalsze ograniczenia spowodowało osiedlenie się tutaj zakonu franciszkanów, których zabudowania znalazły się na osi ulicy.
W XVIII i XIX wieku przy ulicy mieściły się głównie małe dworki oraz niskie kamienice. Po kasacie zakonu w wieku XIX tereny kościelne przejęło państwo, dzierżawiąc je różnym użytkownikom. W latach 1914-1916 Artur Friedman zbudował tu dużą halę targową, którą nazywano Halą Świętojerską lub Feinkinda. Zabudowa ulicy uległa zniszczeniu w 1944 roku. Część odbudowano w latach 1951 i 1956, nawiązując do historycznego stylu Nowego Miasta, ale nie zachowując oryginalnego wyglądu.
Od ulicy Koźlej znajdowało się wejście do znanego klubu warszawskiego "La Madame" zamkniętego po długim i ostrym sporze władz miasta z jego właścicielami oraz bywalcami.