Евгений Самотейкин передал записку Примакова Брежневу, который ее одобрил. Леонид Ильич сам считал, что разрыв отношений с Израилем был шагом эмоциональным и потому недальновидным. Но как их восстановить, если в Москве заявили, что это станет возможным только после полного ухода израильской армии с завоеванных во время войны территорий?
Активным сторонником налаживания секретного канала связи с еврейским государством был председатель КГБ Юрий Владимирович Андропов. В аппарате КГБ не раз предпринимали попытки самостоятельно, в обход Министерства иностранных дел, заниматься внешней политикой. Особые отношения КГБ установил с правительством ФРГ, когда канцлером был Вилли Брандт. Пытались наладить доверительный канал связи с государственным секретарем США Генри Киссинджером, но эту акцию сорвал министр иностранных дел Громыко, который конкуренции не терпел и ревниво относился к любым попыткам вторгаться в его епархию. Что касается Израиля, то в данном случае Громыко не возражал против активности КГБ. Отсутствие дипломатических отношений с еврейским государством исключало участие Министерства иностранных дел.
Тайные контакты были поручены Примакову, организационную сторону взяло на себя КГБ. Миссия была важной, утвержденной решением политбюро от 5 августа 1971 года. С августа 1971 по сентябрь 1977 года Примаков тайно приезжал в Израиль или встречался с израильскими представителями в столице Австрии.
Его собеседниками были руководители страны – премьер-министр Голда Меир и министр иностранных дел Аба Эбан, потом новая команда – премьер-министр Ицхак Рабин, министр иностранных дел Игал Аллон, министр обороны Шимон Перес.
Израильтян, конечно, прежде всего интересовало, кого представляет Примаков, каковы его полномочия. Он отвечал, что «направлен в Израиль с неофициальной и конфиденциальной миссией советским руководством», но не имеет полномочий обсуждать вопрос о восстановлении дипломатических отношений.
Идея состояла в том, чтобы убедить Израиль покинуть занятые в ходе Шестидневной войны 1967 года территории – сектор Газа и Западный берег реки Иордан. Взамен предлагались международные гарантии безопасности Израиля, но Примаков быстро понял, что израильтяне считают такого рода гарантии пустой бумажкой, которая не спасет их в случае нападения арабских стран. Голда Меир напомнила Примакову, как легко в 1967 году были выведены с Синайского полуострова войска ООН, разъединявшие Израиль и Египет, когда это потребовал президент Насер.
Андропов и Громыко предложили согласиться с идеей израильтян «расширить консульскую секцию посольства Нидерландов в Москве». Дело в том, что после разрыва дипломатических отношений интересы Израиля в Советском Союзе представляло голландское посольство. Имелось в виду, что в составе консульской секции посольства в Москве появятся израильские дипломаты и это упростит диалог. Но остальные члены политбюро отвергли предложение председателя КГБ и министра иностранных дел. Слепая ненависть к еврейскому государству лишала Советский Союз возможности играть более важную роль на Ближнем востоке.