Az 1980-as évek végére Magyarországon nyilvánvaló lett az általános gazdasági, politikai és társadalmi válság. Az egyeduralkodó Magyar Szocialista Munkáspárttal (MSZMP) szemben álló, egyre erősebb erők az Ellenzéki Kerekasztalba tömörültek, hogy együttes fellépéssel kényszerítsék a hatalmat demokratikus változásokra. Kemény harc folyt az MSZMP-n belül is az úgynevezett keményvonalasok és a reformerek között, a nézeteltérések egyik sarokpontja éppen 1956 újraértékelése volt. Mindezt fokozódó társadalmi nyomás is ösztönözte: az 1988 tavaszán alakult Történelmi Igazságtétel Bizottsága (TIB) a kivégzettek tisztességes újratemetését és rehabilitálását követelte. Felhívásukra, amelyet a Nagy Imre-perben kivégzettek öt közvetlen hozzátartozója és 34 ötvenhatos elítélt írt alá, 1988. június 16-án a rákoskeresztúri Új köztemetőben 300–400 ember helyezett el koszorút a 301-es parcellában a mártírok feltételezett sírjánál. A Batthyány-emlékmécsesnél tartott tüntetésen a rendőrség tizenhat embert állított elő, miközben a tömeg Nagy Imrét éltette. Ugyanezen a napon Párizsban, a Pére Lachaise temetőben felavatták a forradalom kivégzettjeinek jelképes síremlékét.
1988. november 24-én a TIB felhívással fordult a hozzátartozókhoz, hogy éljenek jogaikkal, és követeljék a jeltelen sírban nyugvó ’56-os áldozatok földi maradványainak kiadását. Öt nappal később az MSZMP KB Politikai Bizottsága határozatot hozott „az ellenforradalmi események kapcsán politikai bűncselekmények miatt elítélt és kivégzett személyekkel kapcsolatos kegyeleti kérdések rendezéséről”, és kapcsolatba lépett az ellenzékkel, a családtagokkal. A kormány 1989. január 26-án úgy foglalt állást, hogy az érintett családok döntenek majd arról, nyilvános temetést rendeznek-e.     Ebben a helyzetben adott interjút a Magyar Rádió 168 óra című műsorának 1989. január 28-án Pozsgay Imre államminiszter, az MSZMP KB Politikai Bizottságának tagja, aki tabut döntve közölte: a Központi Bizottság által felállított történelmi albizottság „népfelkelésnek látja azt, ami 1956-ban történt; egy oligarchisztikus és a nemzetet is megalázó uralmi forma elleni felkelésnek. (...) 1956 nem ellenforradalom volt, hanem egy nemzeti érzékenységében, önbecsülésében a diktatúra által megtiport nép jogos felkelése, népfelkelés.”
Nagy Imre és mártírtársai földi maradványait 1989 áprilisában találták meg, arccal lefelé, kátránypapírba csomagolva. A TIB követelésére május 10-én az Igazságügyi Minisztérium közzétette az 1956. december 20. és 1961. december 13. között a bíróságok által halálra ítéltek és kivégzettek névsorát: az akkori listán 277 ember szerepelt. 1989. február 14-én a TIB az Igazságügyi Minisz­tériummal megállapodott abban, hogy az áldozatok újratemetése június 16-án lesz. Az MSZMP a temetést végül azzal a kitétellel engedélyezte, hogy az legyen a nemzeti megbékélés napja. A Politikai Bizottság május 26-án úgy döntött, hogy az MSZMP hivatalosan nem képviselteti magát a temetésen, de a párt tagjai részt vehetnek rajta. A TIB azt kérte, hogy ne koszorúzzanak azok, akiknek közük volt a megtorlásokhoz.
1989. június 16-án a Hősök terén, a gyász fekete és fehér színeinek drapériájával bevont Műcsarnok lépcsőjén ravatalozták fel Nagy Imre, Maléter Pál, Gimes Miklós, Losonczy Géza és Szilágyi József koporsóját, valamint a tragédia minden mártírját és hősi halottját jelképező hatodik, üres koporsót. A ravatal mellett az áldozatok hozzátartozói, családtagjai, az egykori rabtársak foglaltak helyet, a díszőrséget a TIB, a Politikai Foglyok Szövetsége és más szervezetek képviselői adták. A szertartáson mintegy 250 ezer ember vett részt, az eseményeket élőben közvetítette a rádió és a televízió.
Göncz Árpád mint ’56-os elítélt nyitotta meg a beszédek sorát. Ezután Vásárhelyi Miklós, a TIB elnöke a Nagy Imre-csoport tagjai nevében lépett a mikrofonhoz, és arra figyelmeztetett: „Csak a különbözőképpen gondolkodók és cselekvők kölcsönös türelme és engedékenysége, az előlegezett bizalom szellemében ragadhatjuk meg a kivételes, biztató lehetőséget, csak így biztosíthatjuk a békés átmenetet egy európai, korszerű, szabad és demokratikus társadalomba.” Mécs Imre az ’56-os forradalmi ifjúság képvisele­tében, a vele együtt halálra ítélt bajtársainak nevében azt mondta: „Gyásznap a mai, amikor a nemzet önmaga elvesztett 33 évét veszi számba. A mai nap a korszakváltás határköve is: egy eleve rossz, a nemzet által elutasított, ránk kényszerített és minden tekintetben bukott rendszert temetünk. Megbocsátásról beszélünk, és kéznyújtásról, de kezet majd a szabad választások után, a szabad parlamentben fogunk nyújtani. Addig össze kell fognunk, és akkor a poklok erői sem fognak ki rajtunk.” Mécs Imre ezután felszólította a gyászolókat, egymás kezét fogva esküdjenek meg a vértanúk emlékére, hogy folytatják a harcot a szabadságért. Rácz Sándor mint a Nagybudapesti Központi Munkástanács egykori elnöke azt mondta: „A magyar szabadság előtti első és legnehezebben kezelhető akadály a szovjet csapatok jelenléte Magyar­ország területén. Jelen­létüknek ezek a koporsók az eredményei és a megkeseredett mai életünk is. Ezért kérjük a világ valamennyi becsületes emberét, közösen segítsük hozzá a Szovjetuniót, hogy minél hamarabb kivonhassa csapatait magyar hazánk területéről.” Zimányi Tibor, három rendszer börtöneinek ismerője az internáltak, a recski rabok és a kitelepítettek nevében szólalt fel. „A nemzeti megbékélés jegyében nem akarunk semmi bosszút, semmi kérdőre vonást; a gyilkosok büntetése csupán egy legyen: megneveztetésük” – mondotta. Király Béla, az 1956-os Nemzetőrség parancsnoka a szabadságharcosok nevében mondott beszédet. „Tanuljunk Nagy Imrétől: hazaszeretetet, hogy az egyén boldogságán, az esély egyenlőségén áll vagy bukik a társadalom egyensúlya, hogy 1956 nem vaktában elkövetett tévedések sora, hanem a magyar nemzet őszinte akaratmegnyilvánulása volt. Tanuljuk meg Nagy Imrétől az elveinkért való helytállást, de tudjunk felejteni is, mert aki nem tanul a történelemből, és felejteni sem tud, az megismétli a múlt hibáit és bűneit” – mondta. Utolsóként a magyar fiatalok nevében Orbán Viktor (Fidesz) mondott beszédet. „Valójában akkor, 1956-ban vette el tőlünk, mai fiataloktól jövőnket a Magyar Szocialista Munkáspárt. Ezért a hatodik koporsóban nem csupán egy legyilkolt fiatal, hanem a mi elkövetkezendő húsz vagy ki tudja, hány évünk is ott fekszik. Mi úgy véljük, nem tartozunk hálával azért, hogy 31 év után eltemethetjük halottainkat. Ha hiszünk a magunk erejében, képesek vagyunk véget vetni a kommunista diktatúrának, ha elég eltökéltek vagyunk, rászoríthatjuk az uralkodó pártot, hogy alávesse magát a szabad választásoknak. Ha nem tévesztjük szem elől ’56 eszméit, olyan kormányt választhatunk magunknak, amely azonnali tárgyalásokat kezd az orosz csapatok kivonásának haladéktalan megkezdéséről. Ha van bennünk elég mersz, hogy mindezt akarjuk, akkor, de csak akkor, beteljesíthetjük forradalmunk akaratát” – mondta.
A Hősök teréről 23 halottaskocsi, 30 személyautó és 52 autóbusz vitte a koporsókat, az egyes szervezetek küldötteit és a hozzátartozókat a rákoskeresztúri Új köztemető 301-es parcellájához, ahol az Inconnu-csoport 300 kopjafát állított. A temetőben a koszorúk elhelyezése után felolvasták a kivégzettek névsorát. Az egyházi szertartást kérő hozzátartozók kívánságára különböző felekezetek papjai szentelték meg a sírokat. A síroknál a család által felkértek mondtak búcsúbeszédet, végül a különböző felekezetek papjai ökumenikus imát mondtak és megáldották a 301-es parcellát.
A temetés után nem sokkal, 1989. július 6-án (éppen Kádár János halálának napján) a Legfelsőbb Bíróság Elnökségi Tanácsa Nagy Imre és társai ítéletét hatályon kívül helyezte, és az elítélteket bűncselekmény hiányában felmentette.