Retour à Kotelnitch est le premier long-métrage d'Emmanuel Carrère, avant tout connu comme écrivain. Deux de ses romans ont fait l'objet d'adaptations cinématographiques : La Classe de neige, porté à l'écran par Claude Miller mais dont Carrère a coécrit le scénario (Prix du jury à Cannes en 1998) et L'Adversaire, mis en scène par Nicole Garcia et lui aussi présenté à Cannes, en 2002. Par ailleurs, Emmanuel Carrère a été critique de cinéma pour la revue Positif et le magazine Télérama. Il a publié en 1982 un essai sur Werner Herzog.
Emmanuel Carrère revient sur la genèse du projet : "Marc Lecarpentier, qui était alors le patron de Télérama et qui avait été, il y a longtemps, mon rédacteur en chef, est tombé sur une dépêche racontant la libération et le retour dans son pays d'un type qu'on présentait comme "le dernier prisonnier de la seconde guerre mondiale". Ca l'a intrigué, il m'en a parlé, j'en ai parlé à mon tour à Guilaine Chenu qui venait de prendre en main le magazine Envoyé spécial, et on s'est mis d'accord tous les trois pour faire à la fois un reportage écrit et un sujet de télévision, ce qui était tout à fait nouveau pour moi (...) Cela fait plus de 20 ans que je tourne autour du cinéma (...) mais je ne suis jamais passé à la réalisation et c'était une façon oblique, pas trop intimidante, de l'aborder."
Au terme du reportage tourné pour Envoyé spécial, Emmanuel Carrère désire poursuivre son exploration de Kotelnich afin d'y tourner un film plus long. Après avoir obtenu l'Avance sur recettes, en juin 2002, il retourne donc dans la ville russe, où il retrouve Anna, une jeune femme qui l'avait intrigué lors de son premier voyage. Elle lui avait alors promis des révélations sur le prisonnier hongrois auquel s'était intéressé Carrère, n'était pas venue au rendez-vous fixé, et s'était enfin excusée en arrivant avec sa guitare, à l'hôtel où loge l'équipe du film, pour interpréter quelques chansons. Depuis ce premier voyage, Anna, fiancée d'un officier local du FSB (ex-KGB) est devenue mère. A l'automne 2002, tandis qu'Emmanuel Carrère est rentré en France pour monter la centaine d'heures tournées, le réalisateur apprend une triste nouvelle, qui donne à son film une autre dimension : "Anna et son enfant de huit mois ont été assassiné par un fou", se souvient-il. " C'a été un chox terrible, et ce qui était terrible aussi, c'est de penser que le projet du film consistait à attendre que quelque chose passe et que voilà, quelque chose s'était passé, qui d'une certaine façon débloquait tout, faisant enfin exister le film, et que ce quelque chose, c'était ça, cette horreur."
Retour à Kotelnitch a été présenté en Sélection officielle à la Mostra de Venise dans le cadre de la section "Nouveaux territoires" en 2003. En janvier 2004, le film est présenté en compétition au Festival Premiers plans d'Angers, où il a obtenu le prix spécial du jury ex aequo avec Demi-tarif d'Isild Le Besco.
Emmanuel Carrère tire le bilan de cette expérience particulière : "J'ai l'impression que le retentissement d'une telle expérience résonnera plus tard. Qu'un travail d'accès à la première personne, amorcé depuis quelques années, se poursuit. J'avais mis tant de temps à trouver une place juste dans L'Adversaire, le livre sur Romand, et dans ce film, c'est venu plus naturellement. Ce n'est pas à moi de le dire, mais il me semble que oui, ma place y est juste. J'étais là et je dis : j'étais là. Au fond, j'ai fait et monté ce film exactement comme j'aurais écrit un livre. Avec la même liberté.
Depuis la présentation de son film à Venise, Emmanuel Carrère a décidé de le réduire de vingt minutes. Retour à Kotelnitch durait 2h05, il a été ramené à 1h45.
Emmanuel Carrère est le fils d'une spécialiste reconnue de la Russie, Hélène Carrère d'Encausse, élue en 1999 Secrétaire perpétuelle de l'Académie Française. Ce pays a longtemps laissé l'écrivain indifférent, comme il l'explique : "Pendant presque toute ma vie d'adulte, je ne me suis absolument pas intéressé à la Russie. Je suppose que je m'en tenais prudemment éloigné parce que c'était la chasse gardée de ma mère (...) et que je trouvais le monde assez vaste pour qu'on n'aille pas se retrouver sur son terrain. Mais en entendant parler russe lors de ce premier séjour à Kotelnitch, j'ai éprouvé à la fois un sentiment de familiarité très poignant et de la frustration, presque de la colère, parce que je n'arrivais pas à aligner deux mots de cette langue que, tout de même, j'avais un peu parlé enfant. C'était comme si la musique me revenait, mais pas les paroles."
La musique de Retour à Kotelnitch a été composée par Nicolas Zourabichvili, à qui on doit les partitions des films du georgien Otar Iosseliani. C'est par ailleurs l'oncle d'Emmanuel Carrère, qui a lui aussi des origines georgiennes.
Pour ce film, le réalisateur a travaillé avec Philippe Lagnier, un caméraman remarqué pour ses reportages de télévision. Lagnier a notamment été primé au Festival du scoop et du journalisme d'Angers pour un iflm sur le Kosovo.