Вишеспратница на размеђи Кнез-Михаилове и Коларчеве улице, позната као Палата „Албанија“, препознатљив је мотив многих београдских разгледница које од Теразија ка Калемегдану приказују чувену београдску штрафту. Палата „Албанија“ је саграђена 1939. године на месту где се налазила истоимена кафана.
О томе каква је то кафана била Миленко Тодоровић пише како „у тој кафани ништа није било вредно помена. Столови расклиматани, столњка нигде, шанк стар и дотрајао, посуђе изанђало, патос премазан олајем. Срушена је 1936. и уступила место истоименој палати. Београђани су тешко примили рушење неугледне, али познате кафане, почели су да пристижу у вечерњим часовима и све до поноћи се пило и веселило. Потекла је и покоја суза.“ Чувени комедиограф Бранислав Нушић написао је 1929. године за кафану „Албанија“ и следеће речи: „Постоји и данас, као траг старог Београда и постојаће како изгледа вековима, кафана „Албанија“, ругло Београда, али елдорадо свих закупаца те кафане. Не постоји кафана са мање режије а више промета; нити постоји кафана коју посећује тако разнолика и тако мешовита публика.“
Стара, по описима тако неугледна кафана, сачувана је на многим фотографијама. То је била угаона зграда која је имала приземље, спрат и високи кров. Угао зграде био је засечен и на тој површини се налазио улаз и један прозор. Не зна се поуздано када је ова зграда била саграђена. Претпоставља се да је то било половином 19. века. Стара кафана „Албанија“ срушена је 17. октобра 1936. године.
Историја градње Палте „Албанија“ почиње 8. октобра 1936. године, када је Градско веће донело одлуку да поруши, као дотрајале и нехигијенске, зграде у Кнез-Михаиловој 2 и 4 и Коларчевој 12. Затим је, 14. јануара 1938. године, Хипотекарна банка трговачког фонда расписала конкурс за израду идејног пројекта будуће палате. У конкурсној комисији налазили су се познате архитекте: Петар Бајаловић, Димитрије Леко, Бранислав Којић, Чедомир Петровић и Живојин Јанковић, а један од конкурсних услова био је да „будућа зграда треба да представља монументалан грађевински објекат с обзиром на облик, вредност и прометну живост самога места“.
Чак 84 кандидата учествовала су на овом конкурсу на којем прва награда није додељена. Друга награда је припала загребачком пару архитеката: Хинку Бауеру и Маријану Хадерлеу. Трећенаграђени Бранко Бон и Милан Гракалић такође су били Загрепчани. Инвеститору, Хипотекарној банци трговачког фонда, највише се допао трећенаграђени рад, за који су аутори добили новчану награду од 12.000 ондашњих динара. Разрада пројекта и пројектне документације поверена је архитекти Миладину Прљевићу из Београда. По захтеву инвеститора начињена је допуна идејног пројекта. Згради је додат још један спрат, још један лифт и отворен још један пролаз према Коларчевој улици. Висином, обликом и положајем Палата „Албанија“ постала је доминантна вертикала на једном крају Теразија и на почетку најпознатије улице Београда. Остало је записао да је Хипотекарна банка за парцелу на којој је саграђена „Албанија“ Београдској општини платила 131.500 динара.
Зидање је започето 16. јула 1938. године, а завршено 20. октобра 1939. Шеснаестог децембра исте године издата је дозвола за употребу зграде. У моменту када је изграђена, Палата „Албанија“ је била највиша зграда на Балкану. Пре њеног завршетка највиша зграда у Београду био је хотел „Москва“, а говорило се да је чувени београдски трговац, Влада Митић, желео да на Славији (на простору који је и данас најпознатији као „Митићева рупа“) сагради зграду од 14 спратова која би за два метра надвисила „Албанију“. У књизи Миленка Тодоровића „Београд кога више нема“ поред осталог пише како је Београд те године када је срушена стара кафана „Албанија“ проглашен туристичким местом, да је имао 23 хотела, 433 гостионице, 427 кафана, 412 народних кухиња, 293 здрављака и 318 крчми.