Osiguravajuće društvo „Rosija“ iz Petrograda početkom 20. veka kupilo je imanje na uglu Kralja Milana (danas Terazije) i Balkanske ulice, da bi sazidali objekat za smeštaj svoje firme. Za podizanje zgrade Društvo je raspisalo konkurs 1905. godine. Konkursni zahtevi su propisivali da se pored kancelarijskih prostorija u zgradu smesti i veliki hotel, kafana, restoran i radnje. Prvu nagradu i pravo na realizaciju dobio je rad arhitekte Viktora Kovačića iz Zagreba. Medjutim, uprava Društva u Petrovgradu nije se složila sa izborom žirija, te je prihvatila projekat Jovana Ilkića, nagradjen drugom nagradom. Arhitekta Ilkić pozvan je u Petrograd, gde je rad na projektu nastavljen u saradnji s ruskim arhitektima. Projekat je potpisao arhitekta Pavel Karlovič Bergštreser, „šef-arhitekt“ Osiguravajućeg društva „Rosija“. Zgrada hotela „Moskva“ izvedena je pod nadzorom Jovana Ilkića, odgovornog „za ispravnost izvršenja i konstrukcije“. Zidanje zdanja na Terazijama započeto je u martu 1905, a završeno u decembru 1907. godine. Radove je izvodio Karlo Knol, značajan srpski gradjevinar sa početka prošlog veka, koji je uveo modernu gradnju u Srbiji. Monumentalna ugaona četvorospratnica jedna je od prvih zgrada u Beogradu na kojoj je upotrebljen armirani beton za medjuspratnu konstrukciju, a ovim radovima rukovodio je arhitekta Matija Šnajder.
Zelene keramičke pločice kojima je ostvarena izuzetna dekorativna, koloritna oplata fasade, izradjene su u čuvenoj fabrici majolike i keramičkih ukrasa „Žolnaj“ iz Pečuja. Ukrasni motivi na fasadi izradjeni su prema Ilkićevim nacrtima. Značajne detalje fasade hotela čine skulptura „Žena sa tri deteta“, koja se nalazi u niši na ugaonom delu zgrade, kao i „Glorifikacija Rusije“, alegorijska reljefna predstava privredne i pomorske snage Rusije izvedena u majolici. Zdanje je u unutrašnjoj organizaciji bilo funkcionalno podeljeno u dva dela. Deo palate iz ulice Kralja Milana (danas Terazije) imao je ugostiteljsku i poslovnu namenu. U prizemlju su bila smeštena dva dućana i kafana „Moskva“, na prvom spratu kancelarije Društva „Rosija“, a na ostalim spratovima stanovi za izdavanje. Deo palate iz Balkanske ulice bio je namenjen kafani, restoraciji i hotelu.
Palatu osiguravajućeg društva „Rosija“ sa kafanom i hotelom „Moskva“ otvorio je kralj Petar I Karadjordjević 14. januara 1908. godine. Kafana je ubrzo postala jedno od omiljenih mesta za okupljanja Beogradjana, ali i diplomatskog kora, političke elite, poslovnih ljudi i umetnika. Obimnija restauracija izvedena je u periodu od 1970. do 1972. godine, prema projektu Grigorija Samojlova, Tom prilikom, uvodjenjem galerija u pojedinim prostorijama hotela dobijeno je znatno više prostora, enterijer hotela je ukrašen njegovim vitražima, izvršena je adaptacija hotelskog restorana, izgradjene su dve banket sale i pomoćna odeljenja. Takodje, obnovljene su stara instalacija i oprema (projektanti Milivoje Žugić, Stanko Matović, Kosara Rozman), rekonstruisana je i redizajnirana recepcija hotela i enterijer kafane „Mala Moskva“ (autor Aleksandar Milenković). Godine 2010. Zavod je vršio nadzor nad sanacijom i restauracijom fasada, krova i kupola. Zgrada hotela „Moskva“ utvrdjena je za spomenik kulture 1968. godine, a nakon jedne decenije, 1979. godine, utvrdjena je za kulturno dobro od velikog značaja.