Višespratnica na razmeđi Knez-Mihailove i Kolarčeve ulice, poznata kao Palata „Albanija“, prepoznatljiv je motiv mnogih beogradskih razglednica koje od Terazija ka Kalemegdanu prikazuju čuvenu beogradsku štraftu. Palata „Albanija“ je sagrađena 1939. godine na mestu gde se nalazila istoimena kafana.
O tome kakva je to kafana bila Milenko Todorović piše kako „u toj kafani ništa nije bilo vredno pomena. Stolovi rasklimatani, stolnjka nigde, šank star i dotrajao, posuđe izanđalo, patos premazan olajem. Srušena je 1936. i ustupila mesto istoimenoj palati. Beograđani su teško primili rušenje neugledne, ali poznate kafane, počeli su da pristižu u večernjim časovima i sve do ponoći se pilo i veselilo. Potekla je i pokoja suza.“ Čuveni komediograf Branislav Nušić napisao je 1929. godine za kafanu „Albanija“ i sledeće reči: „Postoji i danas, kao trag starog Beograda i postojaće kako izgleda vekovima, kafana „Albanija“, ruglo Beograda, ali eldorado svih zakupaca te kafane. Ne postoji kafana sa manje režije a više prometa; niti postoji kafana koju posećuje tako raznolika i tako mešovita publika.“
Stara, po opisima tako neugledna kafana, sačuvana je na mnogim fotografijama. To je bila ugaona zgrada koja je imala prizemlje, sprat i visoki krov. Ugao zgrade bio je zasečen i na toj površini se nalazio ulaz i jedan prozor. Ne zna se pouzdano kada je ova zgrada bila sagrađena. Pretpostavlja se da je to bilo polovinom 19. veka. Stara kafana „Albanija“ srušena je 17. oktobra 1936. godine.
Istorija gradnje Palte „Albanija“ počinje 8. oktobra 1936. godine, kada je Gradsko veće donelo odluku da poruši, kao dotrajale i nehigijenske, zgrade u Knez-Mihailovoj 2 i 4 i Kolarčevoj 12. Zatim je, 14. januara 1938. godine, Hipotekarna banka trgovačkog fonda raspisala konkurs za izradu idejnog projekta buduće palate. U konkursnoj komisiji nalazili su se poznate arhitekte: Petar Bajalović, Dimitrije Leko, Branislav Kojić, Čedomir Petrović i Živojin Janković, a jedan od konkursnih uslova bio je da „buduća zgrada treba da predstavlja monumentalan građevinski objekat s obzirom na oblik, vrednost i prometnu živost samoga mesta“.
Čak 84 kandidata učestvovala su na ovom konkursu na kojem prva nagrada nije dodeljena. Druga nagrada je pripala zagrebačkom paru arhitekata: Hinku Baueru i Marijanu Haderleu. Trećenagrađeni Branko Bon i Milan Grakalić takođe su bili Zagrepčani. Investitoru, Hipotekarnoj banci trgovačkog fonda, najviše se dopao trećenagrađeni rad, za koji su autori dobili novčanu nagradu od 12.000 ondašnjih dinara. Razrada projekta i projektne dokumentacije poverena je arhitekti Miladinu Prljeviću iz Beograda. Po zahtevu investitora načinjena je dopuna idejnog projekta. Zgradi je dodat još jedan sprat, još jedan lift i otvoren još jedan prolaz prema Kolarčevoj ulici. Visinom, oblikom i položajem Palata „Albanija“ postala je dominantna vertikala na jednom kraju Terazija i na početku najpoznatije ulice Beograda. Ostalo je zapisao da je Hipotekarna banka za parcelu na kojoj je sagrađena „Albanija“ Beogradskoj opštini platila 131.500 dinara.
Zidanje je započeto 16. jula 1938. godine, a završeno 20. oktobra 1939. Šesnaestog decembra iste godine izdata je dozvola za upotrebu zgrade. U momentu kada je izgrađena, Palata „Albanija“ je bila najviša zgrada na Balkanu. Pre njenog završetka najviša zgrada u Beogradu bio je hotel „Moskva“, a govorilo se da je čuveni beogradski trgovac, Vlada Mitić, želeo da na Slaviji (na prostoru koji je i danas najpoznatiji kao „Mitićeva rupa“) sagradi zgradu od 14 spratova koja bi za dva metra nadvisila „Albaniju“. U knjizi Milenka Todorovića „Beograd koga više nema“ pored ostalog piše kako je Beograd te godine kada je srušena stara kafana „Albanija“ proglašen turističkim mestom, da je imao 23 hotela, 433 gostionice, 427 kafana, 412 narodnih kuhinja, 293 zdravljaka i 318 krčmi.