En 1994, Joseph Koudelka est sollicité par le producteur, Eric Heumann, qui lui demande de suivre la réalisation du Regard d’Ulysse, le film que Théo Angelopoulos est sur le point de commencer à tourner. Il ne s’agit pas pour lui d’être photographe de plateau: on fait appel à Joseph Koudelka pour sa connaissance des Balkans, de l’histoire, car on se trouve en quelque sorte face à deux actualités: celle du tournage du film, et celle de la guerre, une de plus à la fin d’un siècle dont on 
dira qu’il est allé «de Sarajevo à Sarajevo». Durant plus de deux mois, Koudelka a suivi l’équipe de tournage en Grèce, Albanie, Roumanie et en ex-Yougoslavie. Le film obtiendra le Grand Prix du jury à Cannes en 1995. L’une des 
images les plus connues du film montre une gigantesque statue de Lénine embarquée, au bout d’une grue, à bord d’une péniche qui l’emporte jusqu’en Allemagne, destinée à un collectionneur d’objets de brocante… C’est aussi l’une des images les plus marquantes du reportage de Koudelka: mais à l’évidence le rapport à cette icône est bien différent, chez le cinéaste —nostalgique du communisme—, et chez le photographe, longtemps apatride après avoir fui la Tchécoslovaquie en 1969.