После прихода к власти Михаила Горбачева первым контактом стала неофициальная встреча советского и израильского послов во Франции Юлия Воронцова и Овадии Софера в июле 1985 года. Ю.М. Воронцов признавал возможность нормализации отношений, но при условии кардинальных сдвигов в подходе Израиля к урегулированию, его согласия на созыв международной конференции по Ближнему Востоку. Как отмечает В.И. Носенко, «такая позиция отчасти совпадала с установкой, изложенной министром иностранных дел СССР Андреем Громыко в 1973 году на Женевской мирной конференции тогдашнему главе МИДа Израиля Аббе Эвену». В дальнейшем посредником выступил президент Всемирного еврейского конгресса Эдгар Бронфман, посетивший в сентябре 1985 года Москву. Он привез М.С. Горбачеву личное послание тогдашнего премьер-министра Израиля Шимона Переса относительно налаживания диалога. В советском ответе был повторен призыв к коренному изменению Израилем подхода к урегулированию. С лета 1985 года в ЦК КПСС рассматривался вариант направления в Израиль группы консульских сотрудников для решения вопросов, связанных со статусом проживавших там советских граждан и защитой имущественных интересов СССР в этой стране. Инструкции МИДа для этой группы исключали обсуждение любых политических проблем, рекомендовали осуществлять контакты в Тель-Авиве, а не в Иерусалиме, и преимущественно через посольство Финляндии, представлявшее интересы СССР в Израиле. Советские представители категорически отвергли вариант направления аналогичной израильской группы в Москву, сославшись на отсутствие у Израиля в СССР как имущественных интересов, так и своих граждан. В начале 1987 года израильтяне согласились принять советских представителей, не выдвигая собственных условий, хотя и намекнули на желательность взаимности. В июле группа во главе с Георгием Мартиросовым прибыла в Израиль, причем теперь ей поручалось «не уклоняться и от политических контактов». В апреле 1987 года М.С. Горбачев в присутствии президента Сирии Хафеза Асада заявил, что отсутствие дипломатических отношений с Израилем «ненормально»[50]. С июля 1988 года в Москве начали работать израильтяне (группу представителей возглавлял Арье Левин). «На первых порах и советские, и израильские консульские сотрудники сталкивались с большими трудностями – их функции были ограниченны, контакты в обеих странах велись на невысоком рабочем уровне», – признает В.И. Носенко.
Положение стало меняться к лучшему после того, как руководство Израиля выразило готовность направить всю возможную помощь в переживший в 1988 году страшное землетрясение город Спитак в Армении, а также после безоговорочной выдачи Израилем преступников, угнавших в декабре того же года самолет из Минеральных Вод в Израиль. Развитию связей способствовало и смягчение подхода СССР к выезду евреев в Израиль. Еще в начале перестройки из тюрем освободили Анатолия Щаранского и несколько других видных еврейских диссидентов, которым было разрешено покинуть СССР. Число выезжавших евреев неуклонно росло: в 1988-м – 2228 человек, в 1989-м – 1923, с января 1990 по октябрь 1991 года – около 320 тысяч человек. Но эмиграция была сопряжена с многочисленными бюрократическими препонами. До осени 1991-го блокировалось открытие прямой авиалинии Москва – Тель-Авив (самолеты летали преимущественно через Будапешт). «И все же позитивные изменения были очевидны, – подчеркивает В.И. Носенко. – Официальная критика сионизма шла на спад, появлялись отдельные публикации, разоблачавшие антисемитизм. Однако наиболее острые из них проходили с немалыми сложностями. Случалось, что только вмешательство члена Политбюро ЦК КПСС Александра Яковлева открывало возможность их выхода в свет».
В феврале 1989 года министр иностранных дел СССР Эдуард Шеварднадзе и его израильский коллега Моше Аренс встретились в Каире и договорились о контактах между МИДами двух стран. МИД СССР стал постепенно заменять ЦК КПСС в диалоге с Израилем. Последовала серия визитов израильских министров в Москву. В ходе встречи министров иностранных дел СССР и Израиля в Нью-Йорке в сентябре 1990 года было решено заменить консульские группы генконсульствами и тем самым поднять уровень двусторонних отношений. Представительства в Москве и Тель-Авиве были подняты до уровня генеральных консульств 3 января 1991 года. В марте 1991 года в Лондоне глава советского правительства Валентин Павлов встретился с тогдашним премьер-министром Израиля Ицхаком Шамиром. 1 октября 1991 года открылось прямое сообщение чартерными рейсами по маршруту Москва – Тель-Авив.