במרץ 1953 נפטר סטלין, ואת תפקיד ראש ממשלת ברית המועצות ומזכיר המפלגה יורש גריגורי מאלנקוב (Malenkov), מידידיו הקרובים של המנהיג המנוח.
בתגובה, חבר חרושצ'ב לניקולאי בולגנין והשניים החלו לחתור תחת המנהיג החדש.
ההתמרמרות כנגד מדיניות הטיהורים הסטאליניסטית הטתה את הכף, מעמדו של מאלנקוב החל מתערער, והוא נאלץ לפרוש מתפקיד מזכירות המפלגה. בספטמבר 1953 מונה חרושצ'ב לתפקיד.
בפברואר 1955 הודח מאלנקוב מראשות ממשלת ברית המועצות, ואת מקומו תפס בולגנין, בן בריתו של חרושצ'ב.
שנה לאחר מכן, בקונגרס המפלגה ה- 20, נשא חרושצ'ב נאום בו הוקיע את מדיניות הטיהורים ופולחן האישיות של סטלין (תוך התעלמות מהיותו חלק אינטגרלי ממדיניות זו).
היה זה תחילתו של תהליך ה"דה-סטאליניזציה" של ברית המועצות.
מחד, ביסס הנאום מעמדו של חרושצ'ב בקרב מתנגדי הטיהורים, אולם מאידך, היווה שבירת המיתוס הסטאליניסטי זרז להתקוממויות בפולין והונגריה, התקוממויות אשר דוכאו באכזריות על-ידי חרושצ'ב עצמו.
ביוני 1957 הגיע המאבק על השלטון לשיאו, עת חברו אנשי צמרת קומוניסטים שמרנים נגד חרושצ'ב. בסחף האופוזיציה נגרר גם בעל בריתו המסורתי וראש ממשלת ברית המועצות, ניקולאי בולגאנין, ונראה היה כאילו הקיץ הקץ על חייו הפוליטיים של חרושצ'ב.
בעזרתו של שר הביטחון גיאורגי זוקוב (Zhukov), הצליח חרושצ'ב לגבור על יריביו, ובסופו של המאבק יצא כאשר ידו על העליונה; למעשה, שיחקו הקושרים לידיו של חרושצ'ב, ורובם, בהם מאלנקוב, סולקו מן הפוליטבורו ומתפקידי ההנהגה.
באוקטובר סילק חרושצ'ב המנצח גם את ידידו למאבק, זוקוב.
כך, במרץ 1958 התמנה חרושצ'ב ל"פרמייר" - ראש ממשלת ברה"מ ומזכיר המפלגה הקומוניסטית.