1985年3月，戈尔巴乔夫当选苏共总书记，随着外交“新思维”的推行，苏日关系得以再次走向缓和。3月14日，戈尔巴乔夫会见前来莫斯科参加契尔年科葬礼的日本代表团团长、日本首相中曾根康弘时说：苏联愿意同日本发展各个方面的关系，并愿意就此采取实际步骤。苏联外交政策的转变为两国关系的改善带来了新的希望。1986年1月5日，苏联外长谢瓦尔德纳泽带着戈尔巴乔夫的亲笔信访问日本，这是10年来苏联外长第一次访日。苏联改变了多年来根本拒绝承认日苏间存在领土问题的强硬态度，同意将来恢复包括领土问题在内的和约谈判。1986年5月，日本外相安倍对苏联进行了正式友好访问。戈尔巴乔夫在会见安倍时说：只有在认识到不能违反第二次世界大战的结果和边界的不可动摇性的情况下，才能顺利确立友好关系。1991年4月，戈尔巴乔夫访问了日本。戈尔巴乔夫积极谋求改善同日本的关系，日本也筹划乘苏联国内经济困难之机，压苏联让步。由于双方在北方领土问题上意见相左，两国关系并无实际改善。但两国高层领导人的频繁接触，终于使两国关系中的坚冰开始融化。
二、叶利钦时期的俄日关系
冷战结束后，俄日双方为两国关系的改善进行了积极努力。但俄日两国的目标不同，俄罗斯希望获得日本的大规模经济援助，而日本则志在北方领土问题的解决。1993年的《东京宣言》和1997年的“叶利钦桥本计划”似乎表明，双方在各自的立场上有所松动。但两国在政治高层上的灵活和共识，并不意味着两国国内民意的相应转换；相反，俄日两国的政治反对派为赢得选举，不断在敏感的领土问题上大做文章，鼓动民族主义情绪，以至于俄日任何一位当权首脑都无法作出实质性的妥协。由此，俄日两国预定在20世纪末签署和平条约的计划并没有实现。
（一）姗姗来迟的《东京宣言》
戈尔巴乔夫结束他的日本之行不到半年，1991年12月苏联解体，苏日关系为俄日关系所取代。俄罗斯新主政的民主派大力倡导新的外交举措，推动解决与日本的领土之争。这些民主派认为，北方四岛是1945年苏联凭借武力非法获得的，他们希望在内政外交上和苏联彻底决裂，在国际法的基础上解决和日本的领土争端。虽然俄罗斯国内意见并不统一，但当时的外交部主要为民主派所主持，他们在外交政策方面的影响很大；另外，当时俄罗斯政局较为混乱，由于实行“休克疗法”，经济几乎崩溃，叶利钦非常需要大量的资金和援助，因此对日本表示了积极改善关系的愿望。日本借此获得了有利的谈判位置。
1991年9月，叶利钦致函日本首相海部，主张以“法律和正义原则”分阶段解决两国之间的领土争端。1992年2月，俄日工作小组在莫斯科举行会议，集中讨论领土问题。俄方承认以1956年的《苏日联合宣言》为基础解决领土争端。俄日商定，叶利钦将于1992年9月访问日本。1992年5月最高苏维埃议会代表团访问日本，宣布叶利钦访日时将解决领土问题。由此，日本对叶利钦的访问寄予了厚望。
在日本外交部长渡边美治雄为叶利钦访日做准备而对莫斯科进行的访问中，他声明：在北方领土问题上，日本决不会有任何弹性。但这时俄罗斯国内的反对派和军方人士却掀起了强烈的反对声浪，这使得叶利钦的回旋余地变得很小。尽管由于日本的努力，美国等西方国家的领导人也对俄施加了压力，但叶利钦还是在访日的预定日期前四天打电话给日本首相宫泽喜一，推迟访问日本。
1993年4月，叶利钦又宣布将在7月参加东京七国首脑会议前正式访日。
可是到了7月，叶利钦又宣布只参加会议而不对日本进行正式访问。
推迟了两次访日日程后，1993年10月11日，叶利钦终于抵达羽田机场，开始对日本进行正式国事访问。在与细川护熙首相举行会谈后，双方发表了《东京宣言》。俄方确认苏联签署的所有日苏条约依然有效，双方同意就北方四岛的归属问题进行认真的谈判，根据历史事实，在法律和正义的基础上早日解决领土问题，进而签署日俄和平友好条约，使两国关系完全正常化。除此之外，双方还发表了以经济合作为主要内容的《经济宣言》，签署了16个协议文件，包括防止海空事故、和平利用太空合作、文化交流、向俄销毁核武器提供援助合作等。会谈中，叶利钦主动通报日方，驻扎在四岛的俄罗斯军队已撤走了一半，剩下的部分也将撤走，届时只保留边防警备队。
《东京宣言》对日本来说取得了如下重要的收获：宣言明确写明“两国存在领土问题”，并明确列举了齿舞、色丹、择捉、国后四岛岛名；俄日将以过去达成的协议、条约、其他相关文件、法律与正义原则为基础来解决领土问题；东京声明形成了“先解决四岛归属问题”、“然后缔结和平条约”、最后“实现两国关系完全正常化”这种环环相扣的程序；日本为确保“1956年苏联领导人曾经承诺归还齿舞和色丹两岛”的成果，在东京宣言中写入了意味深长的条款：
“俄罗斯作为国家继承了苏联而与苏联具有同一性，日本与苏联迄今所签订的一切条约及其他国际条约，在日本与俄罗斯之间继续适用。”
然而，叶利钦访日后，俄日关系进展并不顺利。由于日本坚持“政经不可分”的原则，“日本实际上并没有打开钱包向俄罗斯提供任何新援助”。1994年10月发生的俄海防部队击沉日本渔船的事件，使刚刚走出低谷的俄日关系再遭挫折。这种状况一直延续到1996年桥本龙太郎就任首相以后，俄日两国关系才再次出现转机。
（二）“欧亚主义”背景下的“多层次接触”
在叶利钦总统的第二任期，普里马科夫取代科济列夫出任外交部长。这一人事变动对俄罗斯外交政策和俄日关系都产生了重要影响。普里马科夫具有较强的欧亚主义理念，强调在加强与西方合作同时，关注亚太地区，注意发展和中国、日本等国家的关系。1996年，两国关系开始出现新的积极变化，俄罗斯虽然坚持搁置领土问题、发展俄日关系的立场，但根据全方位多极化外交政策构想，在寻求和日本的合作方面，采取了更积极的态度。
日本方面注意到了俄罗斯的这个重大变化，并且作出了回应。1997年1月，桥本首相宣布了以“多层次接触”为核心的对俄新政策，即在不放弃领土主权要求的同时，在安全与国际合作等各个层次发展日俄双边交流，谋求在领土谈判、政治对话、安全保障、经济合作、文化交流等各个方面、各个层次同时推进日俄关系。俄罗斯对此十分欢迎，叶利钦于3月发表国情咨文，表示俄愿意与日本发展全方位的合作。
1997年7月24日，桥本龙太郎首相在日本发表关于“欧亚大陆外交”的演说，提出了新的对俄外交政策。桥本声明日本也将从太平洋的视角追求欧亚外交，并提出指导日俄关系的三项原则：（1）互信，即两个邻国的双边关系应该建立在相互信任的基础上；（2）互利，意味着两国都能从发展关系中获得好处，例如归还北方四岛并非“零和”对策，俄罗斯并非单纯失去土地，它可以从中获得许多经济实惠，像经济补偿、确保进入亚太地区、营造作为遵守法律和公平规则的国家形象等；（3）着眼未来，就是说要从长期发展的视角来对待两国关系，主张“不以谁胜谁负的形式解决北方领土问题”。桥本为了让自己的诚意得到俄罗斯的响应，提出了两个友好的建议，一是呼吁两国合作开发西伯利亚和远东地区的能源；二是由日本政府为俄罗斯年轻企业家提供商务培训计划。
对此，叶利钦作出了积极的回应，表示日本外交新方针同俄方的立场、意图是完全一致的，称赞桥本的建议有助于加强发展双边关系。普里马科夫和俄外交部、俄媒体都对桥本的建议，特别是桥本在领土问题上表现出来的灵活立场表示赞赏。俄罗斯舆论将桥本的建议解读为：既然战后50年都没有解决领土问题，说明难度很大，不如留到21世纪让下一代去解决。俄罗斯政府将桥本的建议看做是日本准备改变对俄政策的信号，即将北方四岛的归属同其他双边问题分离开来，暂时搁置领土纠纷，优先考虑双边的经济交流与合作。《消息报》著名评论员康德拉晓夫甚至写道，桥本首相的建议表明北方领土的解决出现了新机遇，日本政府准备冻结领土问题，发展俄日双边关系。
在这个背景下，1997—1998年，俄日关系取得很大进展，两国领导人一年内会晤了三次。其中，给外界印象最为深刻的是1997年11月初在西伯利亚城市克拉斯诺亚斯克举行的不系领带的非正式会晤。这次会议日俄达成了两个重要协定：（1）尽最大努力在2000年缔结和平条约，其中包括领土问题；（2）“叶利钦桥本计划”，其中包括了广泛的政治、经济和财政双边合作计划。
日本承诺积极向俄提供经济援助，主要是：日本政府将向在俄投资的日本私人企业提供担保；日本帮助培训俄经营管理人员；俄日合作改造西伯利亚大铁路等。
这次会晤在两国关系史上是一个里程碑式的事件，意义重大，双方各自取得了自己期待的成果。在日本方面看来，叶利钦承诺在《东京宣言》基础上争取在2000年前缔约，是表明俄有意要解决领土问题。日本还同意叶利钦的建议，两国可以在北方四岛甚至整个千岛群岛进行合作开发，从事大规模的基础设施建设，如渔业加工、道路交通、文化娱乐、港口机场等。此外，桥本答应日本会积极推进执行“叶利钦桥本计划”，保证提供6亿美元的商业贷款和15亿美元的非联系贷款。双方达成的其他协议还有：俄支持日本成为联合国安理会常任理事国；双方将建立两国首脑之间的“热线”联系；签订投资保护协议，进行渔业合作，在发生自然灾害时采取联合救援行动；合作开发新型核反应堆，举行海军联合军事演习等。
1998年4月，俄日两国首脑又在东京西南方向130公里的旅游胜地静冈县川奈市举行了第二次非正式会晤，对“叶利钦桥本计划”作了补充。会晤就两国的经济合作、首脑互访、文化交流、安全保障及太空合作等方面达成了更为具体的协议。在领土问题上，桥本向叶利钦提出了一个非正式的提案，即“川奈提案”，内容有：日俄两国先在北方四岛中最北边的择捉岛以北划定国界，日本可以暂缓要求俄罗斯返还对北方四岛的施政权。但叶利钦对此并没有作出回应。俄日首脑的这两次会晤，为新世纪俄日双边关系的发展、为两国优先发展经济、促进和平稳定的基本方向提供了基本的框架。
第三次会晤是1998年11月小渊惠三正式访问俄罗斯，这是继田中角荣25年前访苏后的日本首相又一次正式访问。俄日两国签署了构筑建设性伙伴关系的《莫斯科宣言》，同时还达成了建立划定边界和北方四岛经济合作委员会的共识。双方还签署鼓励和保护投资的协定并讨论了俄日投资公司的活动计划以及资金的提供。小渊这次访问还给俄罗斯带来了8亿美元的贷款，这笔贷款是“叶利钦桥本计划”的一部分，正式确定贷款意向是在1998年7月，当时两国签订了日本进出口银行提供给俄15亿美元的非联系性贷款协议。
短短一年时间里，俄日就进行了三次首脑会晤，大大促进了俄日经贸关系。1999年3月，在东京召开了有日本私营企业代表参加的远东地区经济研讨会和俄日政府间经贸委员会远东分会，日本政府开始放宽对赴俄从事商务活动的签证。1999年，日本经济管理厅派高级专家赴俄罗斯一年，指导俄经济部制定相关经济结构改革政策。1998—1999年，在日本举办了各种经济培训班，如投资、贸易、企业经营管理等，积极促进日本中小企业和俄罗斯的合作，介绍它们的组织和管理经验。1998—1999年，日本企业联合考察团两次到俄罗斯进行访问。1999年6月，日本驻俄罗斯大使馆组织在俄日本企业代表处考察团前往俄各地考察俄罗斯的区域经济。
这个时期，尽管俄日两国在其他领域主要是经贸领域的双边合作取得了进展，但在领土问题上仍然没有达成谅解，领土问题仍然困扰着两国关系的最终改善。1998年11月，叶利钦总统在与来访的小渊惠三首相会谈时，作为对日方“川奈提案”的回答，向小渊惠三提出了“俄方方案”：搁置领土问题，先缔结和约。这显示叶利钦总统对日政策已发生重大变化，他要把领土问题与缔结和约分开处理。显然，叶利钦已无意再谈领土问题了，这与日本的方针完全相反。同年，俄日成立了以两国外长为主席的“俄日缔结和平条约问题联合委员会”，并在其下设立了“边界划定委员会”和“经济活动联合委员会”，俄日似乎加快了务实的谈判进程。但俄日这种谈判组织结构说明，这正是双方各有所需的妥协体现，即日方急于划定边界，收回四岛；俄方则急于争取日本的经济合作。双方立场南辕北辙，所定的“2000年前缔结和约”的目标根本就是无法实现的。
三、普京时期的俄日关系
普京执政后，俄罗斯从国内权力纷争中摆脱出来，外交上，俄政府更多地关注俄的国家利益；而且，1999年以后，俄经济形势有所好转，俄对经济需求显得不再那么迫切；另外，北方四岛所具有的重要的战略位置、附近蕴藏丰富的渔业资源，再加上俄国的民意状况等因素，都使俄国难以放弃北方四岛。
迈进新世纪的门槛，日本仍然没有走出经济低迷，国内的右翼势力逐渐抬头，日本右翼势力代表石原慎太郎获得广泛的民意支持当选东京都知事、日本首相小泉多次参拜靖国神社都反映了这种潮流。在这样的背景下，日本显然也难以改变对“北方领土”的强硬态度。
（一）“森喜郎—普京计划”
2000年1月，普京出任代总统不久便致信日方，表示将继续执行叶利钦的对日政策，并希望尽快实现两国高层会晤。而日本新首相森喜朗上任不久就向普京表达了访问俄罗斯的愿望。此时的森喜朗陷入了政治信任危机，他想借此机会一举解决领土问题以取得国内的信任，从而躲过这场政治风暴。然而，令森喜朗失望的是，在涉及国家利益问题上，普京显得比他的前任还要谨慎。普京愉快地接受了9月份对日本的访问，也赞赏森喜朗的勇气，但却表示在2000年解决领土问题并签订条约有困难。