1958. június 16-án hajnalban a Kozma utcai Budapesti Országos Börtönben kötél által kivégezték Nagy Imrét, Gimes Miklóst és Maléter Pált. A magyar hatóságok másnap hozták nyilvánosságra az Igazságügy-minisztérium közleményét a „Nagy Imre és társai ellen lefolytatott büntetőeljárásról és az ítéletről”. A nyugati közvélemény és a politikusok „egyöntetű és őszinte megdöbbenéssel, elszörnyedve reagáltak” a hírre, állapította meg Rainer M. János Nagy Imréről írt politikai életrajzának második kötetében, hozzátéve, hogy az egykori miniszterelnök ezúttal „a szovjetellenes szabadságküzdelem tragikus, megcsalatott vezetőjeként jelent meg”. A nyugati kormányok ugyanis a forradalom alatt meglehetős gyanakvással szemlélték Nagy tevékenységét, feltételezve, hogy titokban összejátszik a szovjetekkel.
Miután 1956. november 22-én Jugoszlávia budapesti nagykövetségéről távozva a szovjetek letartóztatták, majd Romániába hurcolták, a forradalom miniszterelnöke szinte teljesen eltűnt a nyugati diplomácia látómezejéből. A szovjet blokk területén szolgálatot teljesítő nyugati külképviseletek krónikus információszerzési nehézségeinek köszönhetően több, később hamisnak bizonyult hír is felröppent az elrabolt Nagy Imre sorsáról. Így például Henri Quioc, a budapesti francia követség tanácsosa 1957. január 2-án arról adott hírt, hogy Nagy nincs többé Romániában, hanem a Szovjetunióba vitték. 1957 szeptemberében Jean Paul-Boncour magyarországi francia követ azt a budapesti amerikai ügyvivőtől származó téves értesülést táviratozta Párizsba, amely szerint Nagy Imre már nincs is börtönben, hanem egy üdülőben tartózkodik a Krímben.
A hidegháború időszakában az egymással szembenálló, a Szovjetunió által vezetett keleti, és az Egyesült Államok dominálta nyugati tömb viszonyában 1958 tavaszán az enyhülés jeleit figyelhetjük meg. Az amerikai, a brit, a francia és a szovjet diplomaták éppen újabb csúcstalálkozó előkészítésén fáradoznak. Ebben a „konstruktív légkörben” jött a budapesti kivégzések híre. Az Észak-atlanti Szövetségbe tömörült országok kormányai kisebb eltérésekkel, de lényegében egységesen reagáltak a magyar hatóságok váratlan bejelentésére. Az olaszok tűntek a legradikálisabbnak.
A NATO Tanács június 19-ei ülésén bejelentették elhatározásukat, hogy ideiglenesen visszahívják budapesti követüket, és egy ideig nem fogják beleegyezésüket adni a magyar kormány római képviselőjének beiktatásához. Javasolták továbbá, hogy a többi szövetséges ország is hozzon hasonló intézkedéseket. Felvetették például, hogy a NATO-országok összes magyarországi diplomáciai misszióvezetőjét rendeljék haza. A francia NATO-nagykövet bejelentése szerint Párizs – az ország közvéleményének felháborodását kifejezendő – szintén megvizsgálta annak lehetőségét, hogy követe időlegesen távozzon Budapestről. A Quai d’Orsay-én úgy vélték, hogy egy ilyen akció akkor lehet sikeres, ha több kormány egyidejűleg megteszi ezt a lépést. A franciák azonban óvtak a túlzottan radikális választól: „…helyes, ha nem keverjük össze a kérdéseket. A Kelet és a Nyugat közötti dialógus más lapra tartozik, és ennek a tétje túl súlyos ahhoz, hogy e téma megítélésében érzelmeink vezessenek minket. A közvélemény, amely ma talán megértené, ha megszakítanánk a párbeszédet Moszkvával Nagy kivégzése miatt, néhány hónap elteltével viszont minden bizonnyal megróna minket ezért. Nem szabad túlságosan sietnünk, és nem szabad visszafordíthatatlan döntéseket hoznunk. […] Mi tehát nem vagyunk hívei a szakításnak…” – szögezte le Franciaország állandó képviselője a NATO Tanácsában 1958. június 20-án. A portugál NATO-delegátus kormánya nevében szintén a Moszkvával való dialógus folytatása, és így az előkészítés alatt lévő csúcstalálkozó megtartása mellett érvelt. A németek ugyancsak. Konrad Adenauer nyugatnémet kancellár nyilatkozata szerint „a felháborodás, amit érzünk, nem riaszthatja vissza a nyugati hatalmakat attól, hogy megegyezést keressenek a Szovjetunióval az általános és ellenőrzött leszerelésről” – olvashatjuk egy AFP-jelentésben. Harold Macmillan brit miniszterelnök június 19-én a parlament alsóházában hasonló véleményének adott hangot, amikor bár „rendkívül tragikusnak” nevezte a magyarországi kivégzéseket, ellenezte, hogy a Nyugat emiatt felhagyjon a szovjetekkel való tárgyalásokkal.
Az amerikai külpolitika irányítói szintén nem kívánták a Moszkvával való kapcsolatok lényeges romlását Nagy és társainak kivégzése miatt. Nem akarták azonban kihasználatlanul hagyni az üggyel kapcsolatban kínálkozó váratlan propagandalehetőségeket. Már a budapesti bejelentéseket követő napokban részletes tervvel álltak elő a NATO Tájékoztatási és Kulturális Kapcsolatok Bizottságában, javasolva, hogy a nyugati szövetségesek „tegyenek a NATO-ban összehangolt propagandalépéseket országaikban annak megakadályozására, hogy a közvélemény elfelejtse a szovjetek magyarországi üzelmeit és azok jelentőségét a szabad világra nézve”. A bizottság többi tagja által is elfogadott álláspontjuk szerint államfők és más első vonalbeli politikusok gyakori nyilatkozatai, amelyekben ezekre a szovjet tettekre emlékeztetnek, különösen alkalmasak „a szovjet hatalom igazi természetének” leleplezésére. Az amerikai külügy javasolta, hogy a NATO-országok koordinálják propaganda-erőfeszítéseiket oly módon, hogy kölcsönösen tájékoztatják egymást a nyilvános állásfoglalásokról és azokról a módszerekről, amelyeket a szovjetek magyarországi magatartásának bemutatására alkalmaznak. Az amerikai tervezet e törekvések szolgálatába kívánta állítani az Egyesült Nemzetek Szervezetét is, amikor az 1957 januárjában az úgynevezett „magyar kérdés” kivizsgálására alakult Ötös ENSZ-bizottság információs tevékenységének felújítására hívott fel.
A washingtoni kormányzat maga is igyekezett megvalósítani ezt a programot. Már a budapesti bejelentés napján, június 17-én az amerikai Külügyminisztérium tiltakozott Nagy Imre és Maléter Pál kivégzése miatt, kifejezve, hogy a magyar forradalom vezetőinek kivégzése „a kegyetlenség megdöbbentő megnyilvánulása”, amiért az alapvető felelősséget a Szovjetunió viseli. John Foster Dulles külügyminiszter úgy vélekedett, hogy a kivégzésekkel a szovjetekkel konfliktusban álló jugoszláv vezetőket akarták figyelmeztetni. Június 18-án maga Dwight D. Eisenhower elnök is nyilatkozott az ügyről. Szerinte a kivégzések újra bebizonyították, hogy a Szovjetunió még mindig „terrort és megfélemlítést” alkalmaz ellenfeleinek leigázására. Hangsúlyozta továbbá, hogy az ítéletek szovjet parancsra születtek, és hogy az ügy „nagyon komoly akadályát” képezi a kelet–nyugati csúcstalálkozónak. Az Egyesült Államok kongresszusa határozatban ítélte el a kivégzéseket.
Az ENSZ Közgyűlésében az 1950-es években még „automatikus többséggel” rendelkező Washington a világszervezetben is támadásba lendült.
Az Ötös Bizottság már június 21-én közleményt adott ki, amelyben sajnálkozását fejezte ki a magyarországi ítéletekkel kapcsolatban, és kinyilvánította törekvését azok hátterének feltárására. Francia diplomáciai iratok tanúsága szerint az amerikai kormány július 11-én bizalmasan konzultált Párizzsal és Londonnal, javasolva az ENSZ rendkívüli közgyűlésének összehívását a bizottság újabb jelentésének megvitatására. Ez alkalmat adott volna a magyar delegáció képviseleti jogának megszüntetésére, Nagyék kivégzésének formális elítélésére és a Kádár-kormány szigorú figyelmeztetésére, hogy állítsa le a további kivégzéseket. A francia és a brit kormány azonban, bár egyetértett az amerikai indítvány céljaival, az újabb közel-keleti válság miatt nem tartotta időszerűnek, hogy megvalósítsák azt. Néhány nap elteltével az amerikaiak is elfogadták ezt az érvet. 1958 májusában ugyanis belpolitikai zavarok kezdődtek Libanonban, aminek nyomán július 14-én Irakban államcsínyre került sor. Ezért érkezett július 15-én 10 ezer amerikai tengerészgyalogos Libanonba és július 17-én 2500 brit ejtőernyős Jordániába. Az Ötös Bizottság jelentésének közgyűlési vitáját mindennek következtében több hónappal elhalasztották. Az ENSZ Közgyűlése 1958. szeptember 22-én határozta el, hogy felveszi XIII. ülésszakának napirendjére a magyar ügyet, amelynek tárgyalására végül csak december 11–12-én került sor.
Az Észak-atlanti Tanács július 16-ai ülésén a Tájékoztatási és Kulturális Kapcsolatok Bizottságának elnöke javasolta, hogy a tanács fogadja el a Nagy Imre és társainak kivégzése kapcsán kidolgozott amerikai propagandaterv ajánlásait. A közel-keleti események miatt azonban ekkorra már az amerikai képviselő sem látta aktuálisnak ennek megvalósítását. Azon volt, hogy vizsgálják meg inkább, hogyan vehetnék rá, „a szovjet propaganda vádjai ellenére”, a világ közvéleményét az angolszász csapatok közel-keleti beavatkozásának támogatására…
Nagy Imre és társai kivégzésének nyugati fogadtatása tehát – az óriási médiafigyelem és a közvélemény heves érzelmi reakciója ellenére – nem volt a kelet–nyugati kapcsolatokat ténylegesen megrontó hidegháborús válság, mivel a nyugati kormányok, akárcsak az 1956-os magyar forradalom idején, ezúttal is pontosan tartották magukat a második világháború nyomán kialakult európai érdekszférarendszer be nem avatkozást előíró játékszabályaihoz.
A kelet-európai népek önállósági törekvéseinek támogatásánál reálpolitikai megfontolásból ezúttal is fontosabb volt a Szovjetunióval való kapcsolat fenntartása és fejlesztése. Ezért nem meglepő, hogy bár Eisenhower elnök június 16-án újságírók előtt még azt mondta, hogy a budapesti kivégzések „nagyon komoly akadályt” jelentenek a szovjetekkel való csúcstalálkozó megrendezése előtt, mintegy két hónappal később épp ezzel ellenkező gesztusnak lehettünk tanúi. Augusztus 22-én az Egyesült Államok, Nagy-Britannia és Franciaország azonos szövegű jegyzékben szólította fel a Szovjetuniót a csúcstalálkozó előkészítését szolgáló diplomáciai tárgyalások felújítására.
Az 1958. júniusi magyar tragédia híre végül a NATO-ban is lekerült a propaganda szintjéről a tárgyilagos elemzés világába. Az 1958. október 8-án a szovjet csatlósállamokról elkészült szakértői jelentés joggal állapította meg, hogy Nagyék kivégzése Moszkva „revizionizmus” elleni harcával függött össze. A korabeli szovjet zsargon e szóval illetett minden olyan kommunizmuson belüli politikai vagy ideológiai törekvést, amely kikezdte Moszkva tekintélyét. A halálos ítéleteket eszerint végső, brutális figyelmeztetésnek szánták nemcsak a már régóta „elhajló” jugoszlávoknak, de a szovjet tömbön belül minden önállóságot fontolgató tényezőnek, elsősorban a Gomulka vezette Lengyelországnak.