1996年的台海危机，加速了中国引进俄制驱逐舰的进程。时任俄国家武器装备出口总局局长卡图京少将回忆，从1996年下半年开始，中国代表团密集访俄，“夜以继日的谈判与陪同参观，让总局的许多同事患上了腰椎病”。次年8月，俄罗斯媒体率先传出消息，称中俄签署了价值8亿美元的军舰采购合同，中方决定购进两艘“现代”级舰及相关武器系统(包括舰载直升机)，工程编号为“956E”，其中字母“E”代表“出口”。
俄方上演“借花献佛”
战舰采购合同签署后，能否按期完工并交付成为中方最关心的因素。为此，俄国家武器装备出口总局盯上了圣彼得堡北方造船厂在建的“叶卡捷琳堡”号和“亚历山大·涅夫斯基”号驱逐舰，打算“借花献佛”，节省两年以上的时间。彼时，囊中羞涩的俄海军拖欠北方造船厂高额货款，已无可能接收这两艘崭新的主力舰。经过俄政府内部折冲，1997年11月21日，北方造船厂与俄国家武器装备出口总局签订合同，将上述两舰转售中国。
由于资金到账及时，两舰的施工进展迅速。1999年7月19日，齐装整备的“叶卡捷琳堡”号离开圣彼得堡，进入波罗的海试航。同年12月25日，该舰降下俄海军旗，更名为“杭州”号，并于次年1月启程前往中国，加入东海舰队。“亚历山大·涅夫斯基”号则于2000年7月开始航行试验，12月交付，更名为“福州”号，同样加入东海舰队。