After two years as Prime Minister (1953–1955), during which he promoted his "New Course" in Socialism, Nagy fell out of favour with the Soviet Politburo. He was deprived of his Hungarian Central Committee, Politburo and all other Party functions and on April 18, 1955, he was sacked as Prime Minister.
Nagy became Prime Minister again, this time by popular demand, during the anti-Soviet revolution in 1956. Soon he moved toward a multiparty political system.
On 1 November, he announced Hungary's withdrawal from the Warsaw Pact and appealed through the UN for the great powers, such as the United States and the United Kingdom, to recognize Hungary's status as a neutral state. Even in this period, Nagy remained steadfastly committed to Marxism; but his conception of Marxism was as "a science that cannot remain static", and he railed against the "rigid dogmatism" of "the Stalinist monopoly".
When the revolution was crushed by the Soviet invasion of Hungary, Nagy, with a few others, was given sanctuary in the Yugoslav Embassy. In spite of a written safe conduct of free passage by János Kádár, on 22 November, Nagy was arrested by the Soviet forces as he was leaving the Yugoslav Embassy, and taken to Snagov, Romania. Subsequently, the Soviets returned him to Hungary, where he was secretly charged with organizing to overthrow the Hungarian people's democratic state and with treason. Nagy was secretly tried, found guilty, sentenced to death and executed by hanging in June, 1958. His trial and execution were made public only after the sentence was carried out. According to Fedor Burlatsky, a Kremlin insider, Nikita Khrushchev had Nagy executed, "as a lesson to all other leaders in socialist countries.
During the time when the Communist leadership of Hungary would not permit his death to be commemorated, or permit access to his burial place, a cenotaph in his honor was erected in Père Lachaise Cemetery in Paris. In 1989, Imre Nagy was rehabilitated and his remains reburied on the 31st anniversary of his execution in the same plot after a funeral organized in part by opponents of the country's communist regime. Over 100,000 people are estimated to have attended Nagy's reinternment.
The collected writings of Nagy, most of which he wrote after his dismissal as Prime Minister in April 1955, were smuggled out of Hungary and published in the West under the title "Imre Nagy on Communism".
Nagy was married to Mária Égető. The couple had one daughter, Erzsébet Nagy (1927-2008), a Hungarian writer and translator. Erzsébet Nagy married Ferenc Jánosi. Imre Nagy did not object to his daughter's romance and eventual marriage to a Protestant minister, attending their religious wedding ceremony in 1946 without Politburo permission. In 1982, Erzsébet Nagy married János Vészi.