In 1957, Khrushchev had defeated a concerted Stalinist attempt to recapture power, decisively defeating the so-called "Anti-Party Group"; this event illustrated the new nature of Soviet politics. The most decisive attack on the Stalinists was delivered by defense minister Georgy Zhukov, who and the implied threat to the plotters was clear; however, none of the "anti-party group" were killed or even arrested, and Khrushchev disposed of them quite cleverly: Georgy Malenkov was sent to manage a power station in Kazakhstan, and Vyacheslav Molotov, one of the most die-hard Stalinists, was made ambassador to Mongolia.

Eventually however, Molotov was reassigned to be the Soviet representative of the International Atomic Energy Commission in Vienna after the Kremlin decided to put some safe distance between him and China since Molotov was becoming increasingly cozy with the anti-Khrushchev Chinese Communist Party leadership. Molotov continued to attack Khrushchev every opportunity he got, and in 1960, on the occasion of Lenin's 90th birthday, wrote a piece describing his personal memories of the Soviet founding father and thus implying that he was closer to the Marxist-Leninist orthodoxy. In 1961, just prior to the 22nd CPSU Congress, Molotov wrote a vociferous denunciation of Khrushchev's party platform and was rewarded for this action with expulsion from the party.

Like Molotov, Foreign Minister Dmitri Shepilov also met the chopping block when he was sent to manage the Kirghizia Institute of Economics. Later, when he was appointed as a delegate to the Communist Party of Kirghizia conference, Khrushchev deputy Leonid Brezhnev intervened and ordered Shepilov dropped from the conference. He and his wife were evicted from their Moscow apartment and then reassigned to a smaller one that lay exposed to the fumes from a nearby food processing plant, and he was dropped from membership in the Soviet Academy of Sciences before being expelled from the party. Kliment Voroshilov held the ceremonial title of head of state despite his advancing age and declining health; he retired in 1960. Nikolai Bulganin ended up managing the Stavropol Economic Council. Also banished was Lazar Kaganovich, sent to manage a potash works in the Urals before being expelled from the party along with Molotov in 1962.

Despite his strong support for Khrushchev during the removal of Beria and the anti-party group, Zhukov was too popular and beloved of a figure for Khrushchev's comfort, so he was removed as well. In addition, while leading the attack against Molotov, Malenkov, and Kaganovich, he also insinuated that Khrushchev himself had been complicit in the 1930s purges, which in fact he had. While Zhukov was on a visit to Albania in October 1957, Khrushchev plotted his downfall. When Zhukov returned to Moscow, he was promptly accused of trying to remove the Soviet military from party control, creating a cult of personality around himself, and of plotting to seize power in a coup. Several Soviet generals went on to accuse Zhukov of "egomania", "shameless self-aggrandizement", and of tyrannical behaviour during World War II. Zhukov was expelled from his post as defense minister and forced into retirement from the military on the grounds of his "advanced age" (he was 62). Marshal Rodin Malinovsky took Zhukov's place as defense minister.

Khrushchev was elected Premier on 27 March 1958, consolidating his power—the tradition followed by all his predecessors and successors. This was the final stage in the transition from the earlier period of post-Stalin collective leadership. He was now the ultimate source of authority in the Soviet Union, but would never possess the absolute power Stalin had.