He joined the Communist Party in 1927, and after graduating from the Leningrad Military-Political Academy, served as a political commissar during World War II.

In July 1953, following the death of Soviet leader Joseph Stalin and the arrest of Beria, the leadership of the Georgian Communist Party was purged by Khrushchev's supporters.

Mzhavanadze left the army and went back to Georgia to lead the Party, replacing Beria's protégé Aleksandre Mirtskhulava as First Secretary in September 1953.

In an unprecedented display of military presence on the political arena, Mzhavanadze was joined in the Georgian Central Committee by the generals Alexi Inauri and Aleksei Antonov.

It has widely been speculated that Shevardnadze had a hand in his boss's downfall; he was certainly the obvious candidate to replace Mzhavanadze.