NOMEN EST OMEN
Legenda kaže da je naziv Palilula potekao od turske zabrane pušenja u varoši zbog straha od požara.
Porobljeno stanovništvo Beograda moralo je da pešači četvrt časa od Šanca, ne bi li se nabavio duvan.
Međutim, do danas je uvreženo mišljenje da legenda, ipak samo legenda. Zbog te, navodne, zabrane ljudi su se slivali u ovo, tada slabo nastanjeno predgrađe, da na miru zadivane i zaduvane.
Postavlja se, međutim, pitanje, kako su se ljudi grejali u Beogradu, tokom dugih i oštrih zima, kako su pripremali hranu, ako je već bilo zabranjeno pravljenje i najmanje vatre zbog visoke izloženosti požaru.
S druge strane, ako je takva zabrana zaista i postojala, ljudi nisu morali da idu daleko. Tako se prihvata teza koja je vezana za današnji Bulevar kralja Aleksandra, koji se u 19. veku nazivao Ulica fišeklija. Čak i decenijama posle promene naziva bio je poznat neformalno kao Fišeklijska ulica. Na početku ove ulice bili su nanizani dućani prodavaca baruta, koji se razmenjivao upravo u fišecima. Sasvim je logično da je tu i u takvoj situaciji bilo zabranjeno paliti lule, pa su ljudi radi toga silazili nizbrdo u pravcu Dunava, u pravcu današnje Palilule.
Žitnica
Prostor današnje Palilule, u vreme mnogobrojnih austrijsko-turskih ratova, kao i kasnije, u vreme oslobođenja u 19. veku, bio je najbliža žitnica beogradskoj varoši i mesto gde se nalazilo najviše useva. Da ne bi dolazilo do požara, na prostoru Palilule je navodno važila zabrana pušenja tokom jednog dela godine. Nakon žetve i odnošenja letine, kada opasnost od požara više nije značila potencijalnu glad, zabrana je dizana. Po ovoj priči, komšije su se tada međusobno dozivale povikom „Pali lulu“, kao znak da je zabrana okončana.
Periferija
Prema trećem „predanju“ svoj naziv Palilula ne duguje ni duvanu, ni požarima, već periferiji, zabačenom delu grada. Na ovoj periferiji mahom su bili siromašniji krajevi, u kojima se vatra iz ognjišta nije pušila kroz skuplje odžake, već kroz „lule“, odnosno proste čunkove probijene kroz zid. Ova se hipoteza uzima i kao najrealnijom od sve tri pretpostavke.
Slučajnost ili ne, tek, danas se sve više ljudi odlučuje da vrevu centra zamene periferijom grada. Ljude, koji se bave prodajom nekretnina, uopšte ne čudi takav trend. Kad je u pitanju prodaja stanova u Beogradu, Palilula ima jednu od najnižih cena po kvadratnom metru u gradu, jeftiniju od Zvezdare i Voždovca, kao i odličnu povezanost sa centrom grada. Ono što ljude tera iz centra grada je stara gradnja, koja, sama po sebi, zahteva velika ulaganja, a i cene kvadratnog metra su skupe. Ostali faktori su i parking mesta, zelene površine, ali i zagađenje vazduha i saobraćajna buka.
Modernizacija
Dolaskom Austrijanaca u prvoj polovini 18. veka Beograd je od orijentalnog, planski počeo da postaje evropski grad. Austrijanci su dosta toga izgradili, a neke od građevina su i danas funkcionalne, kao, na primer, dorćolska Najstarija kuća ili Kapija Karla VI u Donjem gradu.
Zanimljivo je da su Austrijanci izgradili i predgrađe zvano Karlštad. U pitanju je baš današnja Palilula. To je bio zanatski i poljoprivredni kraj, a govorilo se i najlepši u Beogradu.