Сценарий вызывал интерес у многих кинодельцов, но переговоры все они начинали с выдвижения двух условий: во-первых, фильм должен быть англоязычным, во-вторых, главную роль должна сыграть американская звезда. Для Данелии оба этих требования были неприемлемы: в его видении «Паспорт» должен был быть многоязычным фильмом (причем основные задействованные по сценарию языки — это русский, грузинский и иврит). А на главную роль режиссер изначально наметил Бубу Кикабидзе.

В конце концов Данелия сговорился с французским продюсером Константином Александровым — эмигрантом из Ташкента. Александров не возражал против многоязычности фильма, но в главной роли и он непременно желал видеть международную звезду, а не Кикабидзе, знаменитого только в Союзе. Данелия скрепя сердце согласился на это условие.

Вскоре фирма Александрова подписала с «Совинфильмом» договор, согласно которому съемки «Паспорта» в СССР оплачивает советская сторона, а в Австрии и Израиле — французская.

В апреле 1988 года Данелия отправился в США на переговоры с тремя американскими актерами, выбранными им из перечня, предложенного Александровым. Это были Гриффин Данн, Питер Рихард и Николас Кейдж.

В итоге Данн отпал сразу. Рихард подходил Данелии больше, хотя и показался ему староватым для роли Мераба. Агент Кейджа же, узнав о том, что в портфолио ни у Данелии, ни у Александрова нет международных хитов, сразу дал отказ во встрече с актером.

Данелия позвонил своему бывшему ученику Якову Бронштейну, давно живущему в Штатах, и тот просветил учителя, что Кейдж является племянником хорошего данелиевского знакомого Копполы (с последним Данелия подружился в 1979 году, когда Фрэнсис Форд представлял свой фильм «Апокалипсис сегодня» на Московском кинофестивале). В результате Николас Кейдж в тот же день прочел сценарий «Паспорта» и дал свое согласие на участие в этом проекте.

С легким сердцем Данелия отправился в Москву, где немедленно запустил картину в подготовительный период. Георгию Николаевичу удалось настоять на том, чтобы основной костяк съемочной группы состоял из его соотечественников. Оператором стал Вадим Юсов, художником — Дмитрий Такайшвили, композитором — Гия Канчели.

Во время выбора натуры в Израиле у Данелии произошел легкий конфликт с Александровым. Продюсер крепко обиделся на режиссера — и отправил директору «Мосфильма» Владимиру Досталю письмо о том, что отказывается сотрудничать с Данелией.

Взбешенный Георгий Николаевич вернулся в Москву и сразу стал подыскивать себе другой проект. Редактор объединения «Ритм» Роза Буданцева предложила Данелии прочесть сценарий Георгия Николаева «Звездный час по местному времени», который очень понравился режиссеру (в итоге отличный фильм «Облако-рай» по этому сценарию поставит Николай Досталь).

Через месяц Александров прилетел в Москву с извинениями, но Данелия не спешил идти на мировую. Режиссер выдвинул два условия. Во-первых, Александров не должен никак вмешиваться в съемочный процесс. Во-вторых, гонорар за сценарий Данелия потребовал увеличить с десяти тысяч долларов до ста.

После непростых переговоров Георгий Николаевич все же вернулся в проект. Однако теперь в нем не было Кейджа, который, как поведал Александров, передумал сниматься в «Паспорте» (только много позже Данелия узнает истинную причину неучастия Кейджа: сыграв в успешном фильме, Николас внезапно стал большой звездой, и фирме Александрова он уже был не по карману).

Решили было снимать Рихарда, но тот действительно отказался, сославшись на повышенную занятость. В конце концов Константинов предложил кандидатуру французского актера — и прислал Данелии фильм на кассете с его участием (ни актера, ни названия фильма Георгий Николаевич в мемуарах не обозначил).