1984年2月，鄧小平在會見美國客人時指出：中蘇關係正常化的前提是消除三大障礙。如果蘇聯不在消除三大障礙問題上走出一步，兩國關係的戲劇性變化是不可能的。
1985年，戈爾巴喬夫接管蘇聯大權，大力推行其新思維，對內政外交進行了調整。對蘇中關係，戈爾巴喬夫多次表示，希望蘇中關係能得到重大改善，還主張發展政治關係，提高對話級別。
中蘇關係正常化再次遇到了契機。
1985年4月，鄧小平在會見比利時首相時，再次強調：中蘇關係正常化的三大障礙都必須消除，因為都構成對中國的威脅，但如果同時消除有困難，我們同意先從某一個問題開始，比較容易做到的是讓越南從柬埔寨撤軍。
10月9日，鄧小平在會見訪華的羅馬尼亞領導人時說：解決中蘇關係正常化問題、消除三大障礙，首先應從越南從柬埔寨撤軍這件事做起。只要這個問題解決了，其他問題都好解決。鄧小平的這一表態，表現了中國對推動中蘇關係正常化的誠意，也表現了他在消除“三大障礙”上的靈活性和務實精神。與以往的說法相比，中國更為明確地指出，中蘇關係正常化不需要同時解決“三大障礙”，可以先從讓越南從柬埔寨撤軍這一條做起。這一條與蘇聯軍隊沒有直接的關係，相對其他兩條來說，是蘇聯人最容易做到的。如果蘇聯方面這一條都做不到，說明他們缺少實現蘇中關係正常化的誠意。
鄧小平甚至向客人談了對會晤地點的一些具體設想，考慮到羅馬尼亞與蘇聯之間的特殊關係，他請羅馬尼亞領導人帶個口信給戈爾巴喬夫：如果蘇聯同我們達成諒解，讓越南從柬埔寨撤軍，而且能辦到的話，我願同戈爾巴喬夫會見。他還真誠地表示：我出國訪問的歷史使命雖已完成，但為這個問題，我可以破例。這時，鄧小平已經82歲了。一個82歲的老人，還願意為中蘇關係正常化走出國門，這足見他對中蘇關係正常化的誠意和重視。
1986年9月2日，鄧小平在接受美國記者邁克·華萊士的電視採訪時指出，讓越南從柬埔寨撤軍是改善中蘇關係的關鍵。越柬問題使中蘇關係實際上處於熱點和對峙，是中蘇關係正常化的主要障礙。如果戈爾巴喬夫在越柬問題上走出紮紮實實的一步，消除了這個障礙，他願意破例地到蘇聯任何地方同戈爾巴喬夫見面。9月7日，我國政府公開發表了這一談話，作為對戈爾巴喬夫海參崴講話的正式回覆。
但是，對中方所關注的這三個嚴重障礙，蘇方一直堅持反對把蘇中關係改善與這三個問題聯絡在一起。10月3日，蘇聯最高蘇維埃主席團主席葛羅米柯公開表示：蘇聯將擴大與柬埔寨政權的“合作”。
對此，鄧小平在11月16日會見土井多賀子時，再次重申了一年多前中方所提出的關於中蘇最高階會晤的建議和條件。
戈爾巴喬夫在莫斯科會見訪蘇的利比亞總統時也表示：“蘇聯領導人注意到了鄧小平在與日本社會黨委員長土井多賀子的談話”，最高會晤也是蘇方的願望，也可以在任何方便的地方舉行，但是，卻依然堅持認為，柬埔寨問題的解決不是蘇中最高階會晤的前提。對此，他還提出：。“領導人之間所以要舉行會見，正是為了要討論和解決複雜的雙邊和國際關係問題。”
12月4日，鄧小平在會見日本國際貿易促進協會會長櫻內義雄之時，再次鄭重重申了中方的立場。他說：我與戈爾巴喬夫的會見是“有先決條件的，就是蘇聯讓越南從柬埔寨撤軍。如果沒有蘇聯的援助，越南在柬埔寨一天也打不下去”。在談到最高階會晤建議提出一年多來蘇聯方面的態度時，鄧小平不無遺憾地指出：“戈爾巴喬夫拒絕了我的願望。他雖說願意同我會晤，甚至說願意到中國來，但是反對有任何先決條件。”他說：蘇聯領導人事實上是在拒絕最高階會晤，其改善關係的良好願望等等不過是空談。
在中蘇雙方的積極磋商下，蘇聯終於在柬埔寨問題上改變態度，同中方達成諒解。
根據這種情況，鄧小平及時指示，雙方可以進行外長互訪。他說：外長訪問標誌著兩國關係已開始“半正常化”。
1988年12月，時任中國外交部長的錢其琛訪問了蘇聯。這是31年來，中國外長再次踏上蘇聯這片土地。在這次訪問中，雙方深入討論了柬埔寨問題，並就中蘇高階會晤問題交換了意見。在訪問期間，錢其深外長與蘇聯外長舉行了會談，並會見了戈爾巴喬夫。在會見中，蘇方明確表示：“柬埔寨問題是到了該解決的時候了。”對此，中方也同意，在越南撤軍後中國停止對柬的反侵略援助。對此，雙方還同意成立一個專門工作小組進行解決。此外，雙方還就駐蒙蘇軍的撤出、中蘇邊界軍事力量的減少及兩國最高階會晤等同題進行了積極的磋商。對這次會晤的成果，錢其深外長表示，這是“中蘇關係正常化的開始”。蘇聯外長也認為，“蘇中關係現在正在進入一個新時期”。
1989年2月，當時的蘇聯外長謝瓦爾德納澤，對中國進行了回訪，繼續為中蘇高階會晤做準備。在談判過程中，在中方同意蘇方建議的讓戈爾巴喬夫於5月中旬訪華後，蘇方在柬埔寨問題上的態度開始強硬起來。
在上海，錢其深向鄧小平彙報，蘇方在柬埔寨問題上的立場有所後退，他還建議暫不公佈中蘇高階會晤的日期，把這一問題留由雙方繼續商談。聽完錢其琛的彙報，鄧小平堅決地說：中蘇高階會晤日期不能變。
謝瓦爾德納澤在拜見鄧小平時，要求鄧小平確認高階會晤的日期。鄧小平告訴他：“你們兩位外長的談話還沒結束，希望你們繼續工作，日期由你們商定，我聽你們的。”
在返回北京的飛機上，雙方繼續就柬埔寨問題、雙方高階會晤的日期等進行磋商，一直到北京後，仍未達成共識。謝瓦爾德納澤原定離京的時間被迫一推再推。在機場休息廳裡，謝氏與錢其琛繼續進行談判。經協商，謝瓦爾德納澤離京，但蘇方留下人員與我方繼續談判。次日，雙方終於就共同宣告的措辭達成一致，並連同戈爾巴喬夫訪華的日期一起公佈。