パリに住む一匹狼の仕事人・ミレイユは、ある日風変わりな依頼のメールを受ける。ターゲットは夕叢霧香（ゆうむらきりか）という名の少女。一笑に伏すミレイユだったが、添付されたメロディを聞いた途端その場に凍りつく…。
ミレイユのパートナーとして裏の仕事を手伝うことになった霧香。二人のコードネームは「ノワール」。今回のターゲットはフランス国家公安局部長のルグラン。ルグランは裏でテロ組織とつながりを持っていたのだ…。
実業界の大物、デュクスを狙う霧香たち。しかし、それは「ノワール」を仕留めるため、あらかじめ仕組まれた罠だった。デュクスの部下たちに追い詰められる二人。超人的なガンテクニックと機転で危機を脱するかに見えたが、その前に現れたのは…。
クーデターの不穏な空気が漲る小国ウルジア。軍部に付け入りこの国を食い物にしようとするアトライド社の社長ハモンドが今回のターゲット。だが何者かの手により情報がリークされ、霧香とミレイユはウルジア軍に包囲されてしまう…。
自分たちに迫る謎の「敵」の正体を探るため、知り合いの情報屋に調査を依頼するが、情報屋は家族もろとも殺されてしまう。彼の残した手がかりをもとに調査を進める霧香とミレイユの前に立ちふさがる敵の正体は…。
東欧の寒村で人々のために働きながら隠居生活を送る老人。村では聖人とあがめられていたが、彼の正体は元KGBの将校であり、かつて多くの罪なき人々の虐殺を指揮した張本人であった。彼が病に犯され、余命いくばくもないことを知ったミレイユたちは躊躇するが…。
中東の小国で武装ゲリラの指導者を暗殺した二人。だが霧香が負傷し、二人はゲリラに追われることに。なんとか国境へと向かうが、その途中、ミレイユが目を離したすきに霧香が捕えられてしまう…。
謎の組織ソルダとシシリアンの密約書を手に入れるため、マフィア幹部の暗殺を請け負ったミレイユと霧香。マフィアのドンはノワール抹殺のため、シシリアに幽閉していた後継者・シルヴァーナを呼び寄せる。
密約書を奪うため、シルヴァーナと対決することになるミレイユたち。少女時代にシルヴァーナの恐ろしさを体験しているミレイユは気遅れしつつも、シルヴァーナ一派が待ち構えるシシリアに向かう。劣勢を強いられながらも戦うノワール。そして、再びミレイユとシルヴァーナの一騎打ちが…。
今回のターゲットは悪徳警官のルビックと汚職判事のデスタン。だがルビックはノワールの目の前で謎の暗殺者に殺されてしまう。「ノワール」に対する挑戦に、暗殺者の正体をつきとめようと躍起になるミレイユ。いっぽう、ノワールを罠にかけようとするデスタンの前に、謎の暗殺者が現れる…。
謎のコピーの出所を追うミレイユたちに接触してくる謎の男。男はソルダの一員であり、コピーの原本を渡すと言うのだ。ソルダの意図がわからずとまどいながらも、約束の場所に向かう霧香とミレイユ。だが、待ち構えていたのはその男ではなくソルダの刺客たちだった。敵を撃退し、アパルトメントに戻った二人の前に現れたのは…。
NATOの退役将軍ライマンは、引退してスイスの山荘で悠々自適の生活を送っていた。しかし彼はNATOの情報部長でありながらソルダのメンバーだった。「ノワール」との接触を果たしたクロエは、アルテナの指示に従いライマンを粛正に向かう。だがライマンは旧東独国家保安局のゼルナーからも命を狙われていた…。
パリの街。買い物途中の霧香は、公園で絵を描く青年・ミロシュと出会う。彼の絵に興味を持った霧香は、同じ場所で一緒に絵を描くようになる。初めて心を開いた男性とのやすらぎの時間に、ささやかな幸福感を覚える霧香。だが、そんな霧香にミレイユは「もう会わないほうがいいわよ」と水を向ける。いっぽう、かつてミレイユに仲間を殺された犯罪者．ガレが服役を追え、パリに戻ってきていた…。
ミレイユの前に、幼い頃別れた伯父・フェデーが現れる。フェデーはミレイユの両親が殺されたあと、幼いミレイユを連れてコルシカを離れ、ミレイユに裏社会の仕事を教えたその人だった。思わぬ再会に喜ぶミレイユ。だがフェデーはソルダの指示によって、ある仕事を受けていた。フェデーの屋敷に誘われたミレイユが頼まれたこととは…。
ミレイユのアパルトメントに届けられた手紙。それは台湾で仕事を行うよう指示したソルダからの手紙だった。いぶかりながらも台湾に向かう霧香とミレイユ。台湾の裏社会を牛耳る黒社会のボスを暗殺せよというのがソルダの指令だった。二人は協力者の待つ寺院へと向かうが、そこへは既に黒社会の殺し屋たちが迫っていた…。
霧香たちの前に現れた黒社会の暗殺者・シャオリー。彼女は毒爪をもって相手を瞬時に殺害する冷酷な殺し屋だった。敵の手に落ちたミレイユを救おうとする霧香の前に、何故か現れたクロエが協力を申し出る。霧香とクロエの活躍で救出されるミレイユ。混乱の大銃撃戦の中、忽然と姿を消すシャオリー。シャオリーの、そしてクロエの真の目的とは…？
台湾での霧香とクロエの活躍に接して疎外感を隠せないミレイユは、一人コルシカへ旅立つ。現在コルシカを仕切っているベルトニエから、思いがけず両親の仇について情報を得たミレイユは秘密を知る唯一の生き証人、マドランを捜しだすが、マドランは謎の狙撃手に射たれてしまう。 反撃して狙撃手を倒すミレイユ。しかし、そのときクロエが現れ…。
コルシカでクロエに告げられた衝撃の事実にうちひしがれるミレイユは、霧香との間に決定的な溝を感じてしまう。感情を制御できないミレイユに「私の前から消えて」と告げられ、一人なす術もなくパリの街を彷徨う霧香。が、そこにソルダの男が接触してくる。男は「情報を提供する用意がある」と霧香に提案してくるのだが…。
ソルダの男が残した手掛かりをもとに、ついに古文書の正体をつきとめた霧香とミレイユは、その原本を所蔵している実業家・エドリンガーを訪ねるが、そこにまたしてもクロエが現れ、「ノワール」の秘密について語るクロエ。いっぽう、ソルダ最高評議会はアルテナの暴走を阻止すべく、霧香たちのもとに刺客を送り込んでいた…。
パリに戻りはしたが、霧香とミレイユの溝は深まるばかり。そんな二人の元に、ソルダ最高評議会は抹殺のための選りすぐりの「騎士」を送り込む。苦戦の末に敵を撃退する二人だが、そこにまたしてもクロエが現れ、なぜか霧香に向かって銃口を向けるのだった…。
クロエの放った銃弾により、「最後の道しるべ」を受け取った霧香は、さらにクロエから聞かされた事実に衝撃を受け、なすすべもなく雨の中をさまよう。その霧香を狙ってまたしても襲いかかるソルダの「騎士」。たった一人で敵を撃退する霧香だが、その目には狂気の影が潜んでいた…。
ミレイユのもとを離れた霧香は、無意識のうちに荒野をさすらい、気がつくと見知らぬ村の入り口に倒れていた。霧香を救った村人から、ここがソルダの村であると聞かされた霧香は、自分がノワールとしてアルテナの待つ「荘園」への道を歩んでいることを知り、愕然とする。いっぽう、最高評議会は霧香を阻止するため、完全武装の特殊部隊を送り込んできていた…。
霧香と別れたあと、一人パリに残されたミレイユの前に現れた謎の男・ブレフォール。彼はミレイユを「ソルダのメンバーとして迎えたい」と提案する。反撃を試みるミレイユだが、幾多の死線をかいくぐってきたベテラン・ブレフォールの前に銃を下ろしてしまう。アパルトマンに戻り、一人悩むミレイユが、ふとしたことから見つけたものは…。
ついにアルテナの待つ「荘園」にやってきた霧香。アルテナとクロエは霧香を暖かく迎え入れる。ノワ－ル復活の儀式をとりおこなう準備を着々と進めるアルテナたち。魂を失ったかのように状況を受け入れる霧香だが、アルテナから自分の銃を返されたとき、激しい葛藤が霧香を襲う・・・。
儀式の日がやってきた。霧香とクロエを呼び寄せたアルテナは、二人に祝福を贈る。嬉しくてたまらない様子のクロエに対し、あくまで霧香は感情を表に現わさない。泉に向かい、みそぎの沐浴を行う二人の前に現れたのはミレイユだった。しかし、霧香はミレイユに対して銃を向ける・・・。
今や単なる利害を越えたパートナーとして、互いの絆を確かめあった霧香とミレイユは、アルテナの待つ式場へと向かう。すべての事態の報告を受けるアルテナだが、なぜか動じる気配はない。いっぽう、ソルダ最高評議会とブレフォールを乗せたリムジンが荘園へと向かっていた・・・。
