Ülkesinden ayrılıp sürgünde geçirdiği yirmi yılın ardından Prag’ı ziyaret eder. Doğu Avrupa’da fotoğraflar çekmeye başlar.
Anna Fárová, Prag’daki bir Koudelka sergisinin küratörlüğünü üstlenir. Varşova Paktı ordularının şehri işgaline (1968) ilişkin fotoğrafları, ilk kez Çekoslovakya’da sergilenip yayımlanır.
Avrupa’nın doğası en çok tahrip olmuş kesimlerinden birinin, kuzey Bohemya’daki Ore Dağları eteklerindeki alçak tepelerin fotoğraflarını çekmeye başlar; burası, “Kara Üçgen” olarak bilinen ve Güney Almanya ile Polonya’yı da içine alan çok geniş bir bölgenin Batı kesimini oluşturur.
1991
Henri Cartier-Bresson Ödülü’nü alır (Ulusal Fotoğraf Merkezi ve American Express, Paris). Panoramik bir fotoğraf makinesiyle, savaşın yerle bir ettiği Beyrut’un şehir merkezinin fotoğraflarını çeker.
1992
Erna ve Victor Hasselblad Vakfı Fotoğraf Ödülü’nü alır.
Fransız Kültür Bakanlığı’nca Sanat ve Edebiyat Şövalyesi Nişanı’na layık görülür.
1994
“Kara Üçgen” bölgesindeki dört yıllık çalışmanın ardından, panoramik fotoğraflardan oluşan “Cerny trojúhelník - Podkrusnohorí: Fotografie 1990-1994” (Kara Üçgen: Ore Dağları Eteklerindeki Alçak Tepeler) sergi ve kitabını tasarlayıp gerçekleştirir; kitap, Prag’daki Vesmír Yayınevi tarafından yayımlanmıştır.
Theo Angelopoulos’un yönettiği Ulysses’in Bakışı’nın yapımcısının daveti üzerine, Koudelka, kişisel bakış açısıyla, filmin çekildiği Balkan ülkelerinin fotoğraflarını çekmek üzere film ekibine eşlik eder. Bu fotoğraflar, “Periplanissis: Ulysses’in Bakışı’nın İzi Sıra” başlığıyla sergilenip yayınlanmıştır.
1996-97
Bağımsız Saksonya Eyaleti Kültür Vakfı’nın ve Siemens Kültür Programı’nın daveti üzerine, “Aufriss: Künstlerische Positionen zur Industrielandschaft in der Mitte Europas” projesine katılır. Koudelka ve öteki sekiz sanatçıdan, Saksonya, Polonya ve Çek Cumhuriyeti’ni içine alan bölgeye olan tepkilerini fotoğraflarıyla dile getirmeleri istenmiştir; doğası, sorumsuz sanayi sömürüsü ve vahşice yürütülen açık ocak yöntemiyle maden çıkarma yüzünden mahvolmuş bir bölgedir burası.
1997-98
Cardiff’teki Ffotogallery, Cardiff Körfezi Güzel Sanatlar Kurulu adına, sanatçıyı Güney Galler’de bir dizi panoramik fotoğraf çekmekle görevlendirir. Bu projenin doruk noktası, “Reconnaissance: Wales” (Keşif: Galler) kitabı ve sergisidir; buna, Galler’de, başka çalışmalarını bir araya getirerek açtığı öteki sergiler eşlik eder.
1998
“Fotoğraf sanatına olan sürekli, önemli katkısı” nedeniyle, İngiltere’nin Bath şehrindeki Kraliyet Fotoğraf Birliği’nce Yüzüncü Yıldönümü Madalyası’yla ödüllendirilir.
