Dernières années de Staline
Khrouchtchev attribua son rappel à Moscou à la paranoïa de Staline qui craignait des complots à Moscou du même type que ceux qui auraient eu lieu lors de l'affaire de Leningrad où de nombreux hauts-dirigeants du Parti avaient à tort été accusés de trahison. Khrouchtchev redevint le chef du Parti de Moscou et de sa province. Le biographe de Khrouchtchev, Taubman, suggère que Staline avait probablement rappelé Khrouchtchev à Moscou pour faire contrepoids à l'influence de Gueorgui Malenkov et du chef de la sécurité Lavrenti Beria qui étaient largement considérés comme les héritiers de Staline.
À ce moment, le dictateur vieillissant convoquait rarement des réunions du Politburo et l'essentiel des grandes décisions était pris lors de diners organisés par Staline. Ces sessions auxquelles participaient Beria, Malenkov, Khrouchtchev, Kaganovitch, Kliment Vorochilov, Viatcheslav Molotov et Nikolaï Boulganine commençaient avec la projection de films de cowboys que Staline appréciait ; ces derniers avaient été volés à l'ouest et n'étaient pas sous-titrés. Le dictateur faisait servir les repas à 1 h du matin et insistait pour que ses subordonnés restent et boivent avec lui jusqu'à l'aube. À une occasion, Staline demanda à Khrouchtchev, alors âgé de près de 60 ans, de réaliser une danse traditionnelle ukrainienne. Khrouchtchev s'exécuta et indiqua plus tard : « Quand Staline dit danse, un homme sage danse ». Khrouchtchev essayait de faire la sieste après le déjeuner pour ne pas s'endormir en présence de Staline ; il nota dans ses mémoires : « Les choses se passent mal pour ceux qui somnolent à la table de Staline ».

En 1950, Khrouchtchev lança un vaste programme de construction de logements à Moscou. La plupart des immeubles d'habitation avaient cinq ou six étages et il devinrent omniprésents dans toutes l'Union soviétique et existent encore aujourd'hui. Khrouchtchev fit utiliser du béton armé préfabriqué pour accélérer le rythme de construction94. Ces structures construites trois fois plus rapidement que la moyenne à Moscou entre 1946 et 1950, ne disposaient pas d'ascenseurs ou de balcons et furent surnommés Khrushcheby par le public, un jeu de mot sur le mot russe pour taudis, trushcheby. Près de 60 000 000 d'habitants des anciennes républiques soviétiques résident encore dans ces bâtiments.
À son nouveau poste, Khrouchtchev continua son plan de développement des kolkhozes en réduisant le nombre de fermes collectives dans la province de Moscou de 70 %. Cela fit que les fermes étaient trop vastes pour être gérées efficacement par un seul président. Khrouchtchev chercha également à promouvoir son concept d'agro-ville mais lorsque son long discours sur le sujet fut publié dans la Pravda en mars 1951, Staline le désapprouva. Le journal publia rapidement une note indiquant que le discours de Khrouchtchev était une simple proposition et non une politique. En avril, le Politburo désavoua le concept. Khrouchtchev craignit de perdre sa place mais Staline se contenta de se moquer sans prendre de sanctions.
Le 1er mars 1953, Staline fut victime d'un grave accident vasculaire cérébral apparemment après s'être levé de son lit. Staline avait demandé à ne pas être dérangé, ce qui fit que son état ne fut pas découvert avant une douzaine d'heures. Alors que les médecins terrifiés tentaient de le soigner, Khrouchtchev et ses collègues se lancèrent dans une intense discussion en prévision de la formation d'un nouveau gouvernement. Staline mourut le 5 mars et alors que Khrouchtchev et les autres dirigeants restèrent pleurer à côté du lit de Staline, Beria quitta la pièce en demandant sa voiture.
Khrouchtchev commenta sur Staline dans ses mémoires :
« Staline appelait tous ceux qui n'étaient pas d'accord avec lui des ennemis du peuple. Il disait qu'ils voulaient restaurer l'ordre ancien et donc, les ennemis du peuple s'étaient liés aux forces réactionnaires internationales. En conséquence, plusieurs centaines de milliers de personnes honnêtes ont péri. Tout le monde vivait dans la peur. Tout le monde s'attendait à tout moment au coup sur la porte au milieu de la nuit et que ce coup soit fatal... Les personnes qui n'étaient pas du gout de Staline étaient anéanties, des membres honnêtes du parti, des personnes irréprochables, loyaux et travailleurs acharnés de notre cause qui avait suivi l'école de la lutte révolutionnaire sous la direction de Lénine. C'était l'arbitraire total et complet. Et maintenant, tout cela doit être oublié et pardonné ? Jamais! »
Lutte pour le pouvoir
La mort de Staline fut annoncée le 6 mars 1953 de même que la composition du nouveau gouvernement. Malenkov était le nouveau président du conseil des ministres (premier ministre) et Beria (qui consolida son emprise sur les agences de sécurité), Kaganovitch, Boulganine et l'ancien ministre des affaires étrangères, Molotov devenaient premiers députés (vice-présidents). Les membres du Præsidium du Soviet suprême qui avaient récemment été promus par Staline furent écartés. Khrouchtchev fut relevé de ses fonctions de chef du Parti à Moscou pour qu'il puisse se concentrer sur des taches non-spécifiées au sein du Comité centra. Le New York Times lista Malenkov et Beria en première et seconde place en termes d'influence parmi les dix membres du Præsidium alors que Khrouchtchev était dernier100. Le 14 mars, Malenkov démissionna du secrétariat du Comité central101. En septembre, Khrouchtchev fut élu premier secrétaire du Parti par le Comité central. Même avant l'enterrement de Staline, Beria avait lancé une grande séries de réformes qui rivalisent avec celles de Khrouchtchev durant sa période de pouvoir et même avec celles de Mikhaïl Gorbatchev, 30 années plus tard. Les propositions de Beria étaient destinées à dénigrer Staline et à lui faire porter la responsabilité des crimes de Beria101. Une proposition, qui fut adoptée, amnistiait plus d'un million de prisonniers. Une autre, qui ne fut pas adoptée, prévoyait de relâcher le contrôle de l'Allemagne de l'Est au sein d'une Allemagne unie et neutre en échange d'un dédommagement de la part de l'Allemagne de l'Ouest ; Khrouchtchev considérait cette idée comme anti-communiste. Khrouchtchev s'allia avec Malenkov pour bloquer la plupart des propositions de Beria tout en rassemblant le soutien d'autres membres du Præsidium. Leur campagne contre Beria fut aidée par les craintes d'un coup d'état militaire planifié par Beria et, selon Khrouchtchev dans ses mémoires, par la conviction que « Beria aiguisait ses couteaux contre nous ».
Le 26 juin 1953, Beria fut arrêté lors d'une réunion du Præsidium. Il fut jugé en secret et exécuté en décembre 1953 avec cinq de ses associés. Beria fut le dernier perdant d'une lutte de pouvoir soviétique à le payer de sa vie.
La lutte de pouvoir au sein du Præsidium ne fut pas résolue par l'élimination de Beria. Le pouvoir de Malenkov se trouvait dans l'appareil politique civil, qu'il cherchait à étendre en réorganisant le gouvernement et en lui donnant plus de pouvoir aux dépens du Parti. Il tenta également d'obtenir le soutien du public en baissant le prix des produits de base et en abaissant le niveau des ventes d'obligations d'État aux citoyens, qui avaient longtemps été obligatoires. De l'autre coté, Khrouchtchev, dont la base du pouvoir reposait dans le Parti, chercha à le renforcer. Si dans le système soviétique, le Parti devait être l'entité dominante, il avait perdu beaucoup de son pouvoir sous Staline qui avait accaparé l'essentiel du pouvoir pour lui-même et pour le Politburo (puis au Præsidium). Khrouchtchev vit qu'avec un Præsidium divisé par les luttes d'influence, le Parti et son Comité central pouvaient retrouver leur pouvoir d'antan. Khrouchtchev rassembla les soutiens des membres importants du Parti et il parvint à nommer des partisans à la tête des principales instances de pouvoir qui entrèrent ensuite au sein du Comité central.
Khrouchtchev se présentait comme un activiste pragmatique prêt à vaincre tous les obstacles à la différence de Malenkov qui semblait plus terne. Khrouchtchev parvint à faire ouvrir au public le Kremlin de Moscou, une décision qui fut appréciée du peuple. Si Malenkov et Khrouchtchev voulaient tous deux réformer l'agriculture, les propositions de Khrouchtchev étaient plus larges et incluaient la campagne des terres vierges destinée à implanter des centaines de milliers de jeunes volontaires dans des fermes en Sibérie occidentale et dans le nord du Kazakhstan. Malgré des succès initiaux, le projet fut à terme un désastre pour l'agriculture soviétique. De plus, Khrouchtchev disposait d'informations compromettantes sur Malenkov tirées des dossiers secrets de Beria. Alors que les procureurs soviétiques enquêtaient sur les atrocités de Staline vers la fin de son règne, dont l'affaire de Leningrad, il découvrirent des preuves de l'implication de Malenkov. En février 1954, Khrouchtchev remplaça Malenkov sur le siège d'honneur lors des réunions du Præsidium ; en juin, Malenkov cessa d'être au sommet de la liste des membres du Præsidium, qui était à présent organisée alphabétiquement. L'influence de Khrouchtchev continua de s'accroitre avec l'allégeance des principaux représentants locaux du Pari et avec ses candidats à la tête du KGB.
Lors d'une réunion du Comité central en janvier 1955, Malenkov fut accusé pour son implication dans les atrocités et le comité vota une résolution l'accusant d'avoir participé à l'affaire de Leningrad et d'avoir facilité la prise de pouvoir de Beria. Lors d'une réunion du Soviet suprême le mois suivant, Malenkov fut destitué en faveur de Boulganine à la surprise des observateurs occidentaux. Malenkov resta au Præsidium en tant que ministre des centrales électriques. Selon le biographe de Khrouchtchev, William Tompson, « la position dominante de Khrouchtchev au sein des membres de la direction collective ne faisait plus aucun doute ».

À la tête de l'URSS (1955-1964)
Déstalinisation.
Après le recul de Malenkov, Khrouchtchev et Molotov avaient initialement bien travaillé ensemble et le ministre des affaires étrangères proposa même que Khrouchtchev et non Boulganine remplace Malenkov comme premier ministre. Les deux hommes n'avaient cependant pas les mêmes idées politiques. Molotov s'opposait à la campagne des terres vierges et proposait d'augmenter la production dans les régions déjà agricoles ; Khrouchtchev considérait que cela n'était pas possible du fait du manque de ressources et de main d'œuvre expérimentée. Ils s'opposaient également au sujet de la politique étrangère ; peu après sa prise de pouvoir, Khrouchtchev signa un traité de paix avec l'Autriche qui entraina le retrait des forces d'occupation soviétiques. Molotov était réticent mais Khrouchtchev organisa la venue d'une délégation autrichienne à Moscou pour négocier le traité. Bien que Khrouchtchev et les autres membres du Præsidium attaquèrent Molotov lors d'une réunion du Comité central au milieu de l'année 1955 en l'accusant de mener une politique étrangère qui faisait se tourner le monde contre l'URSS, Molotov conserva son poste.
À la fin de l'année 1955, des milliers de prisonniers politiques étaient rentrés chez eux et ils racontèrent leurs expériences du Goulag. La poursuite des enquêtes révéla l'ampleur des crimes de Staline et Khrouchtchev croyait qu'une fois retirée la tache du stalinisme, le Parti inspirerait à nouveau confiance au peuple. À partir d'octobre 1955, Khrouchtchev fit pression pour pouvoir informer les délégués du prochain XXe congrès du Parti communiste de l'Union soviétique des crimes de Staline. Certains de ses collègues dont Molotov et Malenkov s'opposaient à une telle divulgation et ils le persuadèrent de faire ses remarques dans une session fermée au public.
Le XXe congrès du Parti commença le 14 février 1956 et dans le discours d'ouverture, Khrouchtchev dénigra Staline et demanda aux délégués de se lever en l'honneur des dirigeants communistes décédés depuis le précédent congrès. Au matin du 25 février, Khrouchtchev délivra ce qui fut connu sous le nom du « discours secret » devant une assemblée limitée aux délégués soviétiques et interdite à la presse. Durant quatre heures, il démolit la réputation de Staline. Khrouchtchev nota dans ses mémoires que «le congrès m'écouta en silence. Comme le dit le proverbe, on aurait pu entendre une mouche voler. C'était si soudain et inattendu». Khrouchtchev dit aux délégués :
« C'est ici que Staline a montré à de nombreuses reprises son intolérance, sa brutalité et son abus de pouvoir... Il a souvent choisi le chemin de la répression et de la destruction physique, pas seulement contre ses véritables ennemis mais aussi contre des individus qui n'avaient commis aucun crime contre le Parti ou le gouvernement soviétique. »
Le discours secret, s'il ne changea pas fondamentalement la société soviétique, eut de larges effets. Le discours fut un des facteurs ayant mené aux soulèvements en Pologne et à la révolution hongroise plus tard en 1956 et les défenseurs de Staline organisèrent quatre jours d'émeutes dans sa Géorgie natale en juin pour demander la démission de Khrouchtchev et son remplacement par Molotov. Dans les réunions où le discours secret fut lu, les communistes firent des condamnations encore plus virulentes de Staline (et de Khrouchtchev) et demandèrent même des élections multipartites. Cependant, Staline ne fut pas publiquement dénoncé et son portrait resta affiché dans toute l'URSS, des aéroports au bureau de Khrouchtchev au Kremlin. Mikhaïl Gorbatchev, alors un fonctionnaire du Komsomol, se rappela que si les jeunes et les Soviétiques éduqués de son district étaient excités par le discours, beaucoup d'autres le critiquèrent et défendirent Staline ou affirmèrent que cela ne servait à rien de remuer le passé. Quarante ans plus tard, après la chute de l'Union soviétique, Gorbatchev félicita Khrouchtchev pour avoir pris un risque politique aussi grand et pour avoir montré qu'il était «après tout un homme avec un sens moral».
L'expression de « discours secret » se révéla très inadaptée. Alors que l'audience du discours était entièrement soviétique, les délégations d'Europe de l'Est furent autorisées à l'entendre la nuit suivante et sa lecture fut lente pour qu'ils puissent prendre des notes. Le 5 mars, des copies furent envoyées dans toute l'Union soviétique avec la mention « pas pour la presse » au lieu de « top secret ». Une traduction officielle apparut moins d'un mois après en Pologne et les Polonais en imprimèrent 12 000 exemplaires dont un parvint rapidement à l'Ouest. Le fils de Khrouchtchev, Sergueï, écrivit plus tard, «Clairement, Père essaya de faire en sorte qu'il atteignent le plus d'oreilles possibles. Il fut rapidement lu aux réunions du Komsomol, ce qui signifiait 18 millions d'auditeurs supplémentaires. Si vous incluez leurs proches, leurs amis et leurs connaissances, on peut dire que tout le pays fut au courant du discours... Le printemps avait à peine commencé que le discours avait déjà commencé à faire le tour du monde».
La minorité anti-Khrouchtchev au Præsidium fut renforcée par ceux qui s'opposaient à ses propositions de décentraliser la direction de l'économie, ce qui menaçait le cœur de la base du pouvoir de Malenkov. Durant la première moitié de l'année 1957, Malenkov, Molotov et Kaganovitch travaillèrent aux rassemblements de soutiens pour renverser Khrouchtchev. Le 18 juin, lors d'une réunion du Præsidium au cours de laquelle deux partisans de Khrouchtchev étaient absents, les conspirateurs proposèrent que Khrouchtchev soit destitué de son poste de premier secrétaire au profit de Boulganine. Khrouchtchev refusa au motif que tous les membres du Præsidium n'avaient pas été avertis, une objection qui aurait été rapidement balayée si Khrouchtchev ne contrôlait pas fermement l'appareil militaire par l'intermédiaire du ministre de la défense, le maréchal Joukov, et les agences de sécurité. Des réunions prolongées du Præsidium se poursuivirent durant plusieurs jours et alors que les nouvelles de la lutte de pouvoir commencèrent à se répandre, des membres du Comité central, que Khrouchtchev contrôlait, affluèrent à Moscou souvent à bord d'appareils militaires, et demandèrent à participer à la réunion. Leur entrée fut refusée mais il y avait suffisamment de membres du Comité central à Moscou pour organiser un congrès d'urgence du Parti qui força la direction à autoriser une réunion du Comité central. Lors de celle-ci les trois principaux conspirateurs furent surnommés le « groupe anti-Parti » et accusés de complicité dans les crimes de Staline et de promouvoir le factionalisme. Les trois hommes furent exclus du Comité central et du Præsidium, de même que l'ancien ministre des affaires étrangères et protégé de Khrouchtchev, Dmitri Chepilov, qui avait rejoint le complot. Molotov fut muté en tant qu'ambassadeur en Mongolie et les autres furent placés à la direction de complexes industriels et d'instituts loin de Moscou.
Le maréchal Joukov fut récompensé de son soutien avec une place de membre à part entière du Præsidium mais Khrouchtchev s'inquiétait de sa popularité et de son pouvoir. En octobre, le ministre de la défense fut envoyé en tournée dans les Balkans et Khrouchtchev organisa une réunion du Præsidium pour l'écarter. Joukov apprit ce qu'il se passait et se précipita à Moscou uniquement pour recevoir l'annonce officielle de sa destitution. Lors d'une réunion du Comité central plusieurs semaines plus tard, pas un mot ne fut prononcé en défense de Joukov. Khrouchtchev acheva la consolidation de son pouvoir en organisant la démission de Boulganine du poste de premier ministre en sa faveur (Boulganine fut placé à la tête de la Gosbank) et en créant un conseil de défense de l'URSS dirigé par lui-même et qui faisait de lui le commandant en chef des forces armées. Même si la domination de Khrouchtchev était à présent totale, il ne disposait pas du pouvoir absolu de Staline.