凭《致命武器第四集》和《致命罗密欧》在好莱坞崭露头角后，动作巨星李连杰开始酝酿一部集武术、动作英雄和棱角分明的人物于一身的电影，他想到让一名身手不凡的政府特工迷失于人生地疏的异国他乡。“我对拯救世界的超级动作英雄不感兴趣，”李连杰说，“我扮演的刘坚是中国最优秀的特工，他精通武术和针灸，而且作风果敢刚毅，可他并不是超人，当任务最初陷入困境，他完全不知所措。”为了完美呈现故事、人物和关系，李连杰向享誉世界的著名影人吕克·贝松求助，他说：“我喜欢吕克的电影，特别是《这个杀手不太冷》，我知道他能别具一格的聚焦于情节和人物，而且叙事手法也区别于大多数美国影人。”贝松认为李连杰的想法很有潜力，于是决定兼任影片编剧及制作人，并找来罗伯特·马克·卡门联手打造剧本。 　　相识近10年的贝松和卡门曾在《第五元素》中有过合作，卡门在谈到本片剧本的创作经过时说：“我们每天争分夺秒的工作8小时，而且一连就是几周。吕克的专注让我难以置信，他不知疲倦的埋头苦干，不达目的誓不罢休，而且在创作故事的同时，他就已经在脑海中完成了剪辑。”虽说卡门在接手剧本后才有机会见到李连杰，可后者的个性和品行仍对角色的构建发挥着重要作用，卡门说：“在构思刘坚与杰西卡的关系时，我们希望打造出一种充满风趣、戏剧性和人性的情节动力。李连杰是我见过最坦率正直的人，所以刘坚也如出一辙，吕克和我苦心思索何种困境才能让主人公难以应对，除了有半数巴黎警察想置他于死地外，我们还想到让他与妓女为伍。” 　　在完善剧本和物色外景地的同时，贝松决定让出演过《双面女蝎星》（美国版《尼基塔》）的布里吉特·芳达饰演杰西卡，虽然剧本当时尚未完成而且贝松不愿透露影片细节，可芳达还是毫不犹豫的同意接拍，她说：“我相当欣赏吕克的电影，特别是其中的女性角色。当我们见面时，吕克对影片信息守口如瓶，只让我看到了几页剧本，后来我知道他想让我扮演杰西卡，可我却对影片和角色一无所知，不过，我对吕克的作品深信不疑。” 　　本片是法国广告导演克里斯·纳汉的长片处女作，贝松一直看好他的作品，认为他能把握住本片故事中的情感脉络，而纳汉执导本片的最大发现就是李连杰的演技，他原以为李连杰只是功夫过人的动作明星，却没料到功夫之王的演技同样不可小觑。在设计片中动作场景时，李连杰与合作多年的动作指导元奎决定放弃钢丝特技和电脑特效，而是沿用《精武英雄》中基础而真实的街头搏击风格。