El 21 de gener de 1924 va morir Vladímir Ilitx Uliànov, «Lenin». Immediatament, el Govern soviètic va rebre més de 10.000 telegrames de condol, en alguns dels quals es demanava la conservació del cos per a les futures generacions. El 23 de gener, el professor Aleksei Ivànovitx Abrikóssov, un prominent patòleg i anatomista rus, embalsamà el cos de Lenin per mantenir-lo intacte fins al moment del seu enterrament. Aquella mateix nit, l'arquitecte Xtxúsev rebé l'encàrrec de construir un mausoleu en només 3 dies. El dia 26 es decidí situar la tomba a la plaça Roja, al costat dels murs del Kremlin. L'endemà, Xtxúsev construí una tomba de fusta i, aquell mateix dia, s'hi diposità el fèretre de Lenin a dins. Al mes d'agost, Xtxúsev millorà la tomba, alhora que un altre arquitecte, Konstantín Mélnikov, dissenyava un sarcòfag especial per a Lenin.

El 1929 es decidí que el cos embalsamat de Lenin podria preservar-se durant molt més temps i, per tant, s'encarregà un nou mausoleu per substituir el de fusta construït quatre anys abans. Els arquitectes triats van ser el mateix Xtxúsev, Isídor Frantsuz i Borís Iàkovlev. Van usar marbre, pòrfir, granit i d'altres materials de construcció. A l'octubre de 1930 la construcció havia acabat. El 1973, l'escultor Nikolai Tomski dissenyà un nou sarcòfag.

Ja el gener de 1924, l'alcalde de Moscou ordenà que a les portes del mausoleu es disposés una guàrdia d'honor les 24 hores del dia. Els russos l'anomenen el «Sentinella número 1». Després de la crisi constitucional russa de 1993, aquesta guàrdia es dissolgué, i el 1997 va ser traslladada a la Tomba del Soldat Desconegut, als Jardins d'Alexandre.

A l'octubre de 1941, el cos va ser retirat i evacuat a Tiumén (Sibèria), quan semblava que Moscou podria estar en perill imminent de caure en poder de les tropes nazis. Després de la guerra, tornà al seu lloc i es reobrí la tomba.

Entre 1924 i 1972, havien visitat la tomba de Lenin més de 10 milions de persones.

El cos embalsamat de Stalin restà al costat del de Lenin des de la seva mort el 1953 fins al 31 d'octubre de 1961, quan va ser retirat durant la campanya de desestalinització i enterrat a l'exterior de la muralla del Kremlin, darrere del mausoleu.