1956 martındaki Yirminci Kongre'de, Kruşçev'in inanılmaz açıklamalarıyla Stalin'in cinayetleri ortaya döküldüğünde ise, Nâzım Hikmet, bunu Lenin'in geri dönüşü olarak değerlendiren "Yirminci Kongre" adlı şiirini yazdı.


1956 eylülünde ağır bir zatürree geçirdi. 3 Kasım 1956'dan 27 Temmuz 1957'ye kadar, Çekoslovakya'daki Yasenik Sanatoryumu'nda dinlendi.
1957'den sonra, Yazarlar Birliği adına Sovyetler Birliği'nin doğudaki ülkelerine yolculuklar yapmaya başladı. Stalin'in büyük kıyım uyguladığı bu bölgede Türkçe konuşan halklar vardı. Buralarda gerçek dostlar kazanan Nâzım Hikmet, Azerbaycan, Türkmenistan, Özbekistan, Kazakistan'da gördüklerinden, dinlediklerinden çok rahatsız oldu.


Stalin döneminin ağır bir eleştirisi olan İvan İvanoviç Var mıydı Yok muydu? adlı oyunu, 11 Mayıs 1957 günü Moskova Yergi Tiyatrosu'nda sahneye kondu. Bir tek gece oynandıktan sonra yasaklandı. Bu olay Nâzım Hikmet'i çok üzdü. Bayağı bunalıma girdi. İntihar etmeyi bile düşündü. Moskova'da Stalin döneminin baskısı hâlâ duyuluyor, katı komünistler, özgürlükçü komünistlerin önünü kesmek istiyorlardı.
Ama bu oyun daha sonra başka tiyatrolarda, Riga'da, Çekoslovakya'da, Bulgaristan'da vb sahnelendi.


Nâzım Hikmet 1958 mayısını Dino'larla birlikte, Münevver Andaç'ın genç kızlık yıllarının kenti Paris'te, ona gönderme yapan şiirler yazarak geçirdi. Cezaevindeyken yazdığı şiirlerde onu andığı gibi "Gülüm" diyordu, "Paris'te kimi gördün?" sorusunu, "Genç kızlığını Mimi'nin," diye yanıtlıyordu. Oysa 1955 yılı sonlarından beri yeni bir sevda fırtınası yaşamaktaydı. Vera Tulyakova adında genç bir kadına âşık olmuş, onu Moskova'da bırakarak gelmişti. "Sensiz Paris" derken kimin özlemini çektiğini anlamak kolay değildi.
Nâzım Hikmet 1958 haziranında ise Leipzig'e giderek Bizim Radyo'da çalışan Sabiha Sertel, Zekeriya Sertel, Yıldız Sertel'le buluştu. Türkiye'den tanıdığı insanlarla bir araya gelmek ondaki dinmek bilmez memleket özleminin acısını biraz olsun hafifletiyordu.
Münevver ile Mehmet'i İstanbul'da bırakıp gurbete çıkalı yedi yıl olmuştu. Oğlu fotoğraflarda büyüyordu. Ülkesinin insanlarıyla buluşmak onlarla buluşmak gibiydi.


Ama Türkiye'den ayrıldığı 1951 haziranından beri karısına duyduğu ardı arkası kesilmez özlem, Nâzım Hikmet'in başka kadınlarla ilişki kurmasına engel olmamıştı.
1952'de göğsündeki ağrılar yüzünden yatırıldığı Barvikha Sanatoryumu'nda üç ay kadar kalmış, burada kendisine âşık olan Galina Grigoryevna Kolesnikova adında çok genç bir doktor kıza yakınlık duymuştu. Hastaneden çıkınca birlikte yaşamaya karar vermelerini Yazarlar Birliği'nin de uygun görmesiyle, Dr. Galina şairin özel doktoru olarak görevlendirilmişti.
Bu özel doktor gece gündüz Nâzım Hikmet'le ilgileniyor, evini çekip çeviriyor, ilaçlarını veriyor, yemeklerini düzenliyor, dinlenmesini ayarlıyor, yolculuklara birlikte gidiyordu. Şair yıllarca süren bu yakın ilginin birkaç kez kendisini ölümden döndürdüğünü söylerdi.
Dr. Galina onun evli olduğunu, karısını sevdiğini biliyordu. Münevver Andaç'ın çıkıp gelmesine hazırlıklıydı. Bir gün bu iş olursa şairi karısına bırakıp köşesine çekilecekti. Ama bambaşka bir olay yaşandı.


1955 yılı sonlarına doğru, Soyuz Multifilm Enstitüsü'nden Arnavut giysileri konusunda bilgi almak üzere Nâzım Hikmet'i görmeye gelen Valentina Brumberg'in yanında, Vera Tulyakova adında genç bir kadın yardımcı vardı.
Bursa'da 1948 yılı sonunda yaşanan olay bir çırpıda tekrarlanıverdi. Şair gene yaşamında "ilk defa" âşık oluyordu. Ama bu kez gönül verdiği genç kadının evli olduğunu, bir de kızı bulunduğunu bir yıl sonra öğrenecekti.
Elinde çikolatalar, çiçeklerle, Arnavut giysileri konusunda daha fazla bilgi vermek için, Soyuz Multifilm Enstitüsü'ne sık sık gitmeye başladı.
Sevdalandığı genç kadının savaşta ölmüş olan babasından altı yaş daha büyüktü.
Çevrelerindekilerin başlangıçta bir şakalaşma gibi baktıkları ilişki gittikçe ciddileşiyordu.
Ne var ki 1956 eylülünde geçirdiği ağır zatürree Nâzım Hikmet'i uzun süre Moskova'dan uzak kalmak zorunda bıraktı.
3 Kasım 1956'dan 27 Temmuz 1957'ye kadar, dokuz ay, Çekoslovakya'daki Yasenik Sanatoryumu'nda sağlığına kavuşmayı beklerken gene de aklı hep Moskova'daydı.
Vera Tulyakova ayrıldıkları gün ona bu işi daha ileri götürmek istemediğini, dönüşte ilişkilerini sona erdirmeleri gerektiğini söylemişti, ama tam tersi oldu.
27 Temmuz 1957'de Moskova'da buluşur buluşmaz hemen bir ortak iş yaratıp Sevdalı Bulut'un senaryosu üstünde birlikte çalışmaya başladılar. Senaryo kabul edilince arkasından filmin çekimi sırasındaki beraberlik geldi.
Ama Nâzım Hikmet yolculukları yüzünden ikide bir Moskova'dan ayrılmak zorunda kalıyordu. 1957 yılı sonunda bir ay Bakû'deydi, 1958 ocağından nisanına kadar Varşova'da, Mayısta Paris'te, haziranda Leipzig'deyd