2001年的“9·11”事件成为双方关系升温的契机。普京在大国领导人中第一个致电支持小布什，美俄成立了反恐联合工作组。2002年5月，俄罗斯与北约各国签署协议，将常设联合理事会升级为北约-俄罗斯理事会。2004年3月，俄罗斯和9个北约成员国举行了第一次联合反导指挥部演习。2004年12月，俄罗斯与北约批准了全面反恐行动计划，俄加入北约在地中海的反恐行动。时任北约秘书长罗伯逊以及北约一些成员国领导人支持俄罗斯加入北约。这是俄罗斯与北约的短暂蜜月期。

同样在这一时期，俄罗斯与美国和北约关系的三条裂痕开始显现。其一是反导系统与战略稳定问题。2002年，美国单方面退出美苏签订的《反导条约》。其二仍是北约东扩问题。继1999年吸收波兰、匈牙利和捷克为成员国后，北约无视叶利钦此前提出的“北约不向原苏联加盟共和国扩张”的红线，向波罗的海三国在内的7国发出邀请，开启第二轮东扩。波罗的海三国于2004年加入北约。其三是“后苏联空间”的“颜色革命”问题。2003-2005年，乌克兰和格鲁吉亚先后发生“颜色革命”。这三条裂痕虽然在当时并未严重影响双方关系，但成为延续至今的纷争与对峙根源。

裂痕扩大（2006-2013）

2006年后，反导部署、北约东扩、“颜色革命”这三条裂痕不但未能弥合，反而不断扩大。

2006年，美国正式提出在东欧建立反导基地，并前往波兰、捷克、匈牙利、保加利亚等北约新成员国选址。2007年1月，美国启动与波兰、捷克的反导部署谈判。虽然美国声称东欧反导系统是针对“伊朗和朝鲜导弹威胁”，但分析人士认为，该系统同样可用于拦截俄罗斯的导弹，抵消俄核反击能力，削弱俄战略威慑有效性。同年2月，普京在慕尼黑安全会议上发表演讲，激烈批评北约东扩和美国在东欧部署反导系统。这一演讲被视为俄罗斯与美国和北约关系的分水岭。

同时，北约继续推动向俄罗斯近邻扩张。2007年4月，小布什签署法案，支持乌克兰、格鲁吉亚、阿尔巴尼亚、克罗地亚和马其顿加入北约。阿尔巴尼亚、克罗地亚于2009年加入北约。

2009年，奥巴马上任后提出“重启”美俄关系，给俄罗斯与美国和北约关系带来转机。俄罗斯与北约开始朝着改善关系的方向努力，但收效甚微。