Beograd je 1860. godine bio izdeljen na šest kvartova, od kojih je jedan bio Palilula. Tri decenije kasnije, Palilulski kvart bio je najveći u Beogradu. O tome gde se nalazila stara palilulska škola nema pouzdanih podataka, ali na osnovu pisanih izvora može se pretpostaviti da je bila na istom mestu na kojem je izgradjena današnja – više česme pred Jevremovcem postojao je manji objekat namenjen školstvu. Davne 1851. godine, stara palilulska škola imala je samo jedno – muško odeljenje, a prvi učitelj bio je Pavle Atanacković. Četrnaest godina kasnije, škola će dobiti i žensko odeljenje, koje je vodila učiteljica Sofija Subašić. Statistički podaci od tog vremena pa sve do 1914. godine, kada izbija Prvi svetski rat, svedoče o sve većem broju djaka, čak 560, tada već nove i veće palilulske škole, što je zavidan broj u odnosu na stanje drugih obrazovnih ustanova, imajući u vidu dužinu postojanja naseobine Palilula, sa svojim pretežno skromnim, radničkim stanovništvom. Izgradnji ovako značajnog objekta prethodio je dogadjaj koji se odigrao 10. novembra 1892. godine, u čuvenoj beogradskoj kafani „Orač“. Naime, grupa Palilulaca oformila je delegaciju koju su činili gradjani različitih profesija i, samo dan kasnije, tadašnji predsednik Opštine Milovan Marinković prihvata zahtev ove neobične grupe entuzijasta za što skorije podizanje nove školske zgrade, koje je bilo obustavljeno zbog opštinskih nesuglasica.
Za Beograd i Srbiju uopšte, pored gradnje Dorćolske osnovne škole 1893. godine, podizanje Palilulske škole smatrano je presedanom, jer je bila medju prvim školama gradjenim po svim pedagoškim, zdravstveno-higijenskim zahtevima projektovanja školskih zgrada. Od polaganja kamena temeljca 3. aprila 1894. godine, izgradnja objekta trajala je godinu dana. Škola na Palilulskom trgu– izmedju današnjih ulica Takovske, Dalmatinske i Kraljice Marije – svečano je osvećena 16. aprila 1895. godine, kada su svi radovi na objektu bili privedeni kraju. Autor projekta Palilulske škole bio je arhitekta Milan Antonović. Markantna pozicija školske parcele, omedjene sa tri ulice, uslovila je karakterističnu sagledivost zgrade u opštoj vizuri ovog dela grada. Glavna fasada se razvija duž Takovske ulice, a bočne su okrenute ka Dalmatinskoj i Džordža Vašingtona, nekadašnjoj Vidinskoj ulici. Iako vrednost ovog specifičnog prostora danas remete izuzetno prometne saobraćajnice, neposredna blizina značajnih institucija duge tradicije uticala je na formiranje autentičnog istorijskog ambijenta, nadomak užeg gradskog jezgra. Zgrada je zidana opekom u krečnom malteru sa drvenom krovnom konstrukcijom i viševodnim krovom, prvobitno pokrivenim biber-crepom. Projektovana je za 450 djaka sa devet učionica. Enterijer zgrade je funkcionalno prilagodjen potrebama, tako da su učionice rasporedjene u delu objekta ka ulici, dok su sa dvorišne strane hodnici. Od ostalih pomoćnih prostorija izdvaja se svečana sala s pozornicom, koju ukrašavaju pilasteri na zidovima i četiri stuba stilizovanih kapitela. Sagradjena je kao slobodnostojeći monumentalni objekat, razudjene osnove. Ima tri naglašena rizalita, dva bočna i središnji. Oblikovana je u strogom akademskom maniru, s karakterističnom podelom horizontalnim vencem, koji na taj način razdvaja zonu suterena, prizemlja i sprata. Dugački frontovi glavne i dvorišne fasade, kao i njihovi bočni delovi, oživljeni su nizom ritmično rasporedjenih velikih prozora, lučno završenih u prizemlju a pravougaonih formi na prvom spratu. Ovakav raspored i veličina prozora unosili su svetlo u djačke učionice. Poseban akcenat dat je glavnoj fasadi duž Takovske ulice, gde je smešten i glavni ulaz u zgradu. Simetrično postavljena dva dekorativno oblikovana portala (za žensku i mušku decu), daju poseban, svečani izgled objektu, netipičan za školske zgrade. Poznati beogradski trgovac Nikola Spasić je početkom prošlog veka inicirao izgradnju manjeg objekta namenjenog djacima u prostranom dvorištu Palilulske škole, nasuprot glavnoj zgradi. O tome nam svedoči i natpis na samoj zgradi Djačkom skloništu – 1908 – Nikola Spasić. Tu je bila smeštena prva djačka kuhinja u Beogradu, u kojoj se hranilo 150 učenika. Dugo godina je služila kao školska poliklinika Opštine Stari grad, a danas je namenjena djacima prvacima. Izmedju ovih dveju gradjevina 1958. godine je izgradjen novi deo, spratnosti P do P+1, koji je manjom pasarelom spojen sa zgradom iz 1894. godine. Koncipiran je u duhu savremene arhitekture, sa svim tipičnim odlikama školskog objekta sredine 20. veka. Današnji naziv „Vuk Karadžić“ škola je dobila 1931. godine, s jednim kraćim posleratnim prekidom, kad se zvala Osnovna škola broj 6. Utvrdjena je za kulturno dobro 1966. godine.
