同年7月，在马德里举行的北约首脑会议上正式决定，首批接纳波兰、匈牙利和捷克三国加入北约。两年后三国正式成为北约新成员，北约成员就此增至19个。有军事专家指出，北约的这一轮东扩是其实现东扩计划迈出的“实质性一步”。通过首轮东扩，北约将己方防线向东推进了约700—900 公里，将防线进一步抵近俄罗斯的边界，北约的面积增加了 485 万平方公里，人口增加了 6000 万。地面部队增加了近 13 个师，坦克、 空军和海军兵力各增强 15%，北约的战术航空兵甚至可以从波兰境内出发直接威胁到俄罗斯的圣彼得堡、摩尔曼斯克、库尔斯克和沃罗涅日等重要城市。

2002年11月21日，北约在布拉格举行的首脑会议上正式通过了接纳罗马尼亚、保加利亚、拉脱维亚、立陶宛、爱沙尼亚、斯洛文尼亚和斯洛伐克7个国家为北约新成员的决定，2004年3月29日，以上7国正式成为北约新成员。此轮东扩是北约的第二次东扩。也堪称是北约成立以来规模最大的扩充。此轮东扩之后北约成员国从19个变成26个，总人口从7.746亿增至8.199亿，总面积从2338.70万增至2397.98万平方公里，军队的人数从目前的443.75万增到474.76万。北约就此构筑了北起波罗的海，中间经黑海、高加索，直至中亚的“弧形战略防御线”。波罗的海三国的加入卡住了俄罗斯向欧洲“进发”的通道。

2009年4月，阿尔巴尼亚和克罗地亚正式加入北约，从而使该组织成员国总数升至28个，这也是北约的第三轮东扩，通过此次东扩，该组织首次吸纳西巴尔干地区国家入约，意义非同寻常，不仅俄罗斯的安全空间进一步缩小，欧洲的地缘安全格局也被大大改写。值得一提的是，在此轮东扩前，北约就已将乌克兰列为“北约候选国”。而2008年爆发的格鲁吉亚南奥塞梯事件和乌克兰政治内乱，使得乌克兰“入约”计划暂时搁浅。也是在此之后，普京果断采取行动，开始强势对抗北约的围追堵截，不仅在克里米亚举行公投火速将其并入俄罗斯，同时也大力支持乌克兰东部的卢甘斯克、顿涅茨克等地区的武装势力与政府军作战。