2000年9月3日，普京启程对日本进行访问。他在访日前夕的记者招待会上明确表示：俄罗斯承认与日本存在领土问题，但“谈不上俄罗斯将南千岛群岛交给日本的问题”。
在随后的会谈中，森喜朗再次谈到1998年日方要求先划定国界、后协商行政管理权的“川奈提案”。普京表示不能接受“川奈提案”，但表示承认两国间存在的问题，准备继续对话，尊重两国间的协议，明确表示继承1956年的《日苏联合声明》，即缔结和平条约后归还齿舞群岛和色丹岛。普京提出划定国界与和平条约脱钩，先缔结中间性的友好条约。森喜朗则予以拒绝，并指出中间性条约将导致领土问题搁置。
第三轮会谈后，森喜朗和普京签署并发表了包括六项内容的《关于和平条约问题的联合声明》。对于领土争端问题，声明指出：双方同意，依据迄今达成的所有协议，包括1993年关于日俄关系的《东京宣言》、1998年日俄两国关于构筑建设性伙伴关系的《莫斯科宣言》，为通过解决择捉岛、国后岛、色丹岛和齿舞群岛的归属问题而签订和平条约继续谈判。
尽管日俄首脑未能在解决领土问题上取得实质性的进展，但从具体成果来看，双方以能源开发为中心的“森喜朗—普京计划”，以及关于核裁军方面的合作等，都是互有所求并出于现实和长远的政治、经济利益考虑的。由此而言，虽然领土问题并无进展，但普京访日之行对日俄双方来说，还是有所收获的。
2001年3月25日，森喜朗和普京在俄罗斯远东城市伊尔库茨克再次举行首脑会谈。会谈结束后，双方发表了《伊尔库茨克声明》，确定了1956年《日苏联合宣言》的法律效力，但俄方对日方强烈要求的重新设定签订和约新期限的要求未予接受，只表示愿意为尽快找到两国均能接受的解决方案而加紧谈判。
此时，森喜朗的内阁支持率已降至9%，四个在野党已经就再次向国会提出对森喜朗内阁的不信任案达成协议，执政联盟内也出现要求森喜朗下台的呼声。所以，森喜朗极想通过推动日俄关系的进展，在北方领土与和平条约问题上有所收获，以帮助自己渡过政治危机。但由于日俄关系的复杂性，森喜朗的愿望显然并不现实。伊尔库茨克首脑会晤一个月后，森喜朗下台了。
2001年4月24日，在自民党总裁选举中，59岁的前卫生部长小泉纯一郎获胜，成为短短的一年时间里日本上任的第三位首相。
（二）《俄日行动计划》
2003年1月，小泉首相正式访问俄罗斯，这次访问除了上述日本对俄关系困境之外，还有如下背景：小泉首相上任一年来，在国内高举改革大旗，但国内经济毫无起色，这对其争取连任首相非常不利，何况要恢复停滞10年的日本经济绝非易事。为此，小泉急于寻找外交政绩。小泉首先想到了要借助中日关系，为此做出了不少重要姿态，如参观卢沟桥和卢沟桥抗日纪念馆等。但由于小泉要争取国内右翼保守势力的选票，三度参拜靖国神社，引起中、韩强烈抗议。小泉2002年9月对北朝鲜进行了“破冰之旅”，试图通过打破日朝关系来建立政绩。但是，小泉访朝非但未能改善日朝关系，反因“日本人被绑架问题”，使得日朝关系更加恶化了。在对华、对韩、对朝外交进展不利的情况下，小泉选择了俄罗斯作为其外交的突破口。
此外，日本也意识到了，从亚太中、美、日、俄四大国关系来看，日俄关系是最弱、最疏远的。2002年，川口外相访俄时强调：在国际关系中，“日俄关系应该互补”，“日美中俄的相互关系对于东北亚地区的发展与稳定有重大意义，但其中最弱的是日俄关系，这对双方都是一个损失”。
小泉访俄的主要成果是：确认两国具有“自由、民主、法制、人权”等共同的价值观念；两国领导人发表了《俄日行动计划》，决定首脑定期会晤制度化；积极利用国际会议之际进行两国首脑会晤；在日本首相官邸和克里姆林宫之间设立“热线”，并通过经常性的电话会谈使两国首脑对话活跃化；两国外长也将积极保持接触；构建两国军事、经济领域各种对话机制和体制。
但是小泉此次访俄，在最关键的北方四岛问题上未获得任何实质性的进展。这完全是意料之中的结果。
普京总统希望日本开展对俄罗斯的经济、技术、贸易合作，但俄难以在北方四岛问题上满足日本的要求，于是，只能在日本最希望的其他政治目标方面满足日本的要求，争取日本对俄经济技术支援。俄罗斯在此次《俄日共同声明》中确认：“俄罗斯支持日本成为联合国安理会常任理事国。”作为回报，日本在声明中也明确做出了一系列的承诺：对于俄罗斯欲积极参加亚洲事务，特别是东亚事务，日本表示将“积极促进两国包括在东盟地区论坛等在内的亚太地区的合作，日本欢迎俄罗斯参加亚欧首脑非正式会议活动的努力”；“日本支持俄罗斯参加世贸组织”，并允诺“根据俄需要，将向俄提供必要的知识和经验”。
俄日两国在朝鲜半岛上也有共同利益。小泉强调：“由于俄罗斯在传统上和朝鲜保持着密切关系，所以我们希望俄罗斯能在解决这一问题上扮演关键角色。”俄罗斯和日本都希望把朝鲜半岛上现存的“2+2对话体制”（南北朝鲜+美国、中国）扩大为“2+4对话体制”（俄罗斯和日本加入该对话体系内）。为此，《俄日共同声明》表示：“两国就建立东北亚安全保障多边对话框架之可能性而进行合作。”
日本对于与俄开展能源合作也表现出了空前的热情。小泉在2003年1月10日与普京举行会谈时，动员俄罗斯建设从东西伯利亚到纳霍德卡的输油管道。这是对中俄已经达成的协议，从东西伯利亚到大庆管线的竞争提案。普京的回答很慎重，他表示：我对此非常感兴趣，但是存在如何确保资金等问题。
小泉对莫斯科的这次访问，在领土问题上双方依然没能取得进展，但是两国在有利于各自利益的领域拓展了合作关系。
（三）领土问题再起波澜
正当俄日两国的关系因双方各自的利益需要而在逐渐好转之际，特别是在关于俄远东石油管道走向的问题上，日本展开了全方位、高层次的外交攻势，俄罗斯也予以积极回应，日俄之间一度出现了友好的氛围之时，日本政坛却平添变数。因为不满小泉出兵伊拉克的政策和养老金改革方案，在2004年7月的参议院选举中，执政的自民党意外地输给了在野的民主党。虽然靠与公明党的联合得以维持政权，但小泉还是能够感觉到压力的存在，特别是其一直所标榜的改革事业并未取得像样的成绩。此时，小泉更需要在外交上有所突破，以缓解民众的不满情绪。小泉出于自身政治利益的考虑，不惜以日俄关系为代价，显示其收复北方领土的决心。
这样，2004年，俄日双方在领土问题上再次掀起新一轮的较量。首先是日方在领土问题上的态度再次坚定起来。7月，日本政府提出对俄外交新方针，转变了近年来“不偏重北方领土问题而全面发展两国关系”的做法，重新确定将领土问题作为双方谈判重点的立场。
新方针除了强调两国首脑外交的重要性以及日本要从正面就领土问题与俄方展开交涉外，还决定将1993年由当时俄总统叶利钦和日首相细川护熙共同签署的《东京宣言》作为交涉的“基本文件”。因为在这一文件中，日俄双方就解决北方领土问题后早日缔结和平条约等事宜达成了共识。新方针还否定了以往有关“先归还两岛”的阶段性解决方案，重申要一揽子解决四岛的归属问题，并表示不拘泥于普京的“早日访日”，等到日俄和平条约谈判有望取得进展的阶段实现普京访日也不迟。
2004年9月2日，日本首相小泉没有理会俄方的抗议，乘坐日本海上保安厅的巡逻船对北方四岛进行了近距离视察。此前，小泉的这一视察计划刚一披露，俄罗斯官方就发表声明表示抗议。俄驻日本大使洛修科夫称：“如果小泉首相这样做的话，有关北方领土问题不但不会因此得到解决，反而会引起新的麻烦。”
与此同时，为了打破僵局，俄方也向日方抛出了“橄榄枝”。
2004年11月14日，俄罗斯外长拉夫罗夫就俄日争议领土问题发表讲话，称可能遵守《1956年宣言》，把北方四岛中的齿舞、色丹两岛交给日本。次日，普京在同内阁成员会谈时，对拉夫罗夫的上述言论表示赞赏。普京再次明确俄联邦愿意承担苏联的所有国际义务，包括履行《1956年宣言》。