Jest to ulica idąca od Targowej do Szwedzkiej. Przeprowadzona została około roku 1865 w związku z budową Dworca Petersburskiego, który usytuowano wzdłuż Wileńskiej, frontem do niej. Była główną ulicą Nowej Pragi, biegła wzdłuż torów kolejowych.
Od początku istnienia wjeżdżała w nią kolejka konna łącząca, przez ulice Targową i Zygmuntowską, Dworzec Petersburski z Terespolskim (obecnie Wschodni) i Warszawsko-Wiedeńskim. Nazwa ulicy wiąże się z jej północno-wschodnim kierunkiem oraz z tym, że z Dworca Petersburskiego odchodziły pociągi do Wilna.
Początkowy odcinek Wileńskiej przed dworcem między Targową i Konopacką zaprojektowano jako szeroką ulicę, dalsza część od Konopackiej do Szwedzkiej była znacznie węższa, ciaśniejsza i zadymiona parowozami i pobliską stalownią, dlatego zwano ją Czarnowileńską lub Ciemnowileńską.
Około roku 1900 pod nr 63/65 wybudowano Dom Pracy dla młodzieży im. Mańkowskiej oblicowany czerwoną cegłą. Po stronie nieparzystej na przełomie wieków XIX i XX ulicę zabudowano kamienicami mieszkalnymi trzy- i pięciopiętrowymi. Koło 1909 roku przez Wileńską od Targowej do Konopackiej przeprowadzono tramwaj elektryczny. Sześć lat później Dworzec Petersburski został spalony. Zamiast niego wzniesiono tymczasowy budynek Dworca Wileńskiego usytuowany w innym punkcie, frontem do Targowej. Na miejscu Dworca Petersburskiego przy rogu Wileńskiej i Targowej ok. 1930 roku powstał gmach Warszawskiej Dyrekcji Kolei. Za gmachem tym w ostatnich latach przed wojną postawiono kilka domów mieszkalnych dla kolejarzy.
Zabudowa Wileńskiej, z wyjątkiem dwóch domów, ocalała podczas ostatniej wojny. Około 1950 roku skasowano tramwaj jadący przez Wileńską, przez co ulica straciła znaczenie arterii komunikacyjnej.