19世紀末、アルビオン王国は革命により、首都ロンドンを境にして、旧来の王国と新しく生まれた共和国の二つに分かれた。 そしてその境界には、お互いの国交を断絶させるため『ロンドンの壁』が作られた・・・。 王国へ送り込まれた共和国のスパイ・アンジェは、チームリーダーのドロシーとずば抜けた剣技を持つちせと共に、共和国へ亡命を望んでいる王国の研究者の青年・エリックを、王国側の妨害にあいながらも無事保護する。保護した先は、アンジェ達が任務で通っているクイーンズ・メイフェア校の資料室。そこでエリックが出会ったのは、付き人のベアトリスを従えた王国のプリンセスであった。彼女は笑顔で言う、「実は私、共和国のスパイなんです」と。彼はその告白に驚きながらも、突如、任務にないことを要望する。 「もう一人、亡命させたい者がいる」 エリックの願いは果たして聞き入れられるのか？

時間はさかのぼる― まだプリンセスがアンジェ達の仲間になる前の話。 プリンセスと容姿が酷似していたアンジェは共和国側のスパイ組織・コントロールから、王国のプリンセスと入れ替わる『チェンジリング作戦』という任務を与えられる。プリンセスに接近するため、クイーンズ・メイフェア校に転入するアンジェ。先にメイフェア校に生徒として潜入していたドロシーと合流するも、プリンセスの傍らには常に衛兵がおり、またプリンセス自身がベアトリス以外に親しい友人を作らないことから、安易な接触は難しいと判断。そこで二人はプリンセスが参加する外務卿主催のパーティーへ潜り込み、そこでプリンセスとコンタクトをとろうとする。 しかし、この時、会場ではもう一つの重大な事件が起こっていた……。

敵側である共和国のスパイ・アンジェ達と手を組んだプリンセス。 だが、プリンセスの友人でもあり侍女のベアトリスは、プリンセスと瓜二つであるアンジェに対して、アンジェがプリンセスと入れ替わってその地位を利用し、王国に被害を与えるのではないか？と疑念を抱く。 そして警戒心を強くし、プリンセスは自分が守らなければと心に誓っていた。 そんなある日、共和国スパイの総元締めであるコントロールから、プリンセスに指令が入る。 それはアンジェ達に協力し、共和国側から盗まれた、紙幣の原盤を取り戻すミッションであった。

王国がついにケイバーライト制御装置の小型化に成功した。 この小型化が普及すれば王国側が世界大戦を起こす可能性もある。 事態を重く見た共和国のコントロールは、ドロシーにその試作品の奪取を命じる。 その際、ドロシーはLから、今回のミッションは王国側に大きな被害を出すためプリンセスが裏切る可能性があることを示唆され、プリンセスの動向を見張るよう極秘任務を言い渡される。 プリンセスの立場を利用し、無事、研究施設に潜入したアンジェ達だったが、ケイバーライトの研究室はすでにもぬけの殻となっていた。果たしてそれはプリンセスの差し金なのか？

日本からの外交特使・堀河公とその使節団が、条約改正を求めて王国へ訪れた。 極東の島国からやってきたその一団を出迎えることになったプリンセスだが、裏では藤堂十兵衛という人物による堀河公暗殺の噂が流れていた。 暗殺騒ぎにプリンセスが巻き込まれることを案じたコントロールは、アンジェ達にメイドとして同行するよう指令を下す。 かくして王室専用列車によるロンドンへの旅路が始まるが、その途中とある少女が忍び込む。 いち早く侵入者の存在に気付いたアンジェは、暗殺者の存在を疑い、その少女……ちせと対峙する。

ある日、コントロールから別の任務を言い渡されるドロシー。 それは、死亡した連絡員の身体に埋め込まれた、王国外務省の暗号表を奪取するというものであった。 任務を言い渡した7によると、該当の死体はノルマンディー公の協力者が知っているという。 ベアトリスと共にロンドン中の死体が集まるモルグへ潜入したドロシーは、既に死体探しを始めていたノルマンディー公の協力者と接触するが、なんとそこにいたのはドロシーの生き別れた父親・ダニーであった。

王国から共和国への亡命を希望しているオライリー卿。 彼が秘密裏に接触する人物を特定するよう指令を受けたアンジェ達は、ターゲットが現れるまでオライリー卿が借りている部屋を監視することに。 公園で見張りをすることになったアンジェだったが、スリを失敗しては相手からひどい仕打ちを受ける少女・ジュリと出会う。 数日の任務期間中にジュリと親しくなったアンジェは、クロトカゲ星の“王女”と“スリ”の話を語りきかせるのだった——。

ちせがクイーンズ・メイフェア校に転入してから半月。 食事や学業、芸術の分野にいたるまで──西洋文化に慣れないちせは、東洋の島国・日本から来た留学生ということで、校内でも浮いた存在だった。 校内で問題行動を起こしては、アンジェから目立つ行動を咎められることも少なくない。 そんなある日、ちせはクイーンズ・メイフェア校に通うある貴族の子弟と諍（いさか）いになり、事件を起こしてしまう・・・。

スパイ養成所でアンジェとドロシーの同期生だった委員長。 彼女と共に機密文書奪取の命令を受けたアンジェ、ドロシー、ベアトリスの三人。 任務は無事終了したかに見えたが、アンジェとドロシーにはもう一つの指令が与えられていた。

アンジェとドロシーに告げられた新たな任務は、プリンセスの暗殺だった。 急ぎプリンセスのもとへ駆けつけたアンジェだったが、既にコントロールから派遣されたゼルダがプリンセスの護衛という名で監視についていた。 さらに、ドロシーとちせまでもがアンジェの前から姿を消してしまう。

革命軍の女王暗殺計画を知ったプリンセスは革命を止めようとするが、プリンセス暗殺の失敗を察したゼルダがプリンセスに銃口を向ける。 一方アンジェはプリンセスの真意を確認するため、飛行船を脱出するが……