Komitet partyjny zlecił przygotowanie projektu architektom miejskim, jak szacowano koszty budowy miały wynieść ponad 100 tysięcy rubli. Budowla miała móc mieścić około 3 tysięcy ludzi, jednak projekt przedstawiony przez architektów okazał się niezadowalający – był mało monumentalny i nie odznaczał się niczym szczególnym, uznano więc, że był niegodny osoby Lenina. 22 marca ogłoszono konkurs na nowy projekt, z terminem zgłoszeń do 30 marca. Ostatecznie po wielu sporach wybrano projekt lokalnego architekta, który (po nałożeniu kilku poprawek) zakładał wybudowanie czteropiętrowego budynku z kolumnową fasadą.
thumb|left|250px|Dom Lenina w 1926 roku. 1 maja 1924 roku w Święto Pracy nastąpiło uroczyste wmurowanie kamienia węgielnego pod budowę obiektu. Inwestycję planowano ukończyć jeszcze tego samego roku, ale braki w materiałach, sprzęcie oraz ludziach uniemożliwiły zrealizowanie tego pomysłu. Z powodów propagandowych już 21 stycznia 1925 roku - w pierwszą rocznicę śmierci Lenina - oddano do użytku część pomieszczeń budynku, które zaczęły być natychmiast użytkowane do różnych celów. Ostateczne ukończenie budowy nastąpiło 1 maja 1925 roku, dokładnie w rok po wmurowaniu kamienia węgielnego. Dom Lenina ozdobiono wieloma ornamentami o symbolice radzieckiej. Balkon na głównej fasadzie stylizowany był na moskiewskie Mauzoleum Lenina.