舞台は江戸国。近未来かと思える科学技術が現代より進んだ日本国の北関東に、３０年前に、江戸時代の生活を残した地域が独立して建国された江戸国。世界の承認は得られなかったものの、日本国は自治権を認め、属領扱いとする。鎖国状態で、日本との行き来はわずか。
主人公は日本国の大学生佐藤辰次郎。両親が離婚し、母と暮らしていたが、母を交通事故でなくす。その後、父と会った。父はガンにおかされ、余命半年と診断されていた。その父から江戸へいくことを頼まれた。辰次郎は、江戸で生まれたが、５才の時に日本国へ来たのだとはじめて知らされた。
普通は江戸国へ入るのは難関で、すぐには許可されないが、なぜか、辰次郎は初めての申請が認められ、江戸へいくことになる。一緒にいくのは、年上の会社勤めをしていた松吉と世界を旅して回っている奈美。
辰次郎がすんなり江戸入国が許されたのは、江戸の方でも辰次郎を必要としていたからだった。彼が落ち着き先として指定されたのは、評判の一膳飯屋金春屋。と思ったら、実はその裏にある長崎奉行所の出張所。そしてそのボスが長崎奉行の金春屋ゴメスだった。容貌魁偉で狂暴なゴメスは誰もが恐れる存在だったが、実は女性で、思慮深い奉行だった。
江戸では何度か鬼赤痢と呼ばれる原因も治療法もわからない病が起こったことがある。普通の赤痢と違うところは、生存率がゼロに近いこと。唯一の例外が辰次郎だった。５才の時にかかった辰次郎を助けたい一心で、両親は江戸から出て日本へいった。しかし、なぜか、日本についた頃には、辰次郎にはなんの症状もなくなっていた。
その道中の何かが、病を癒したと思ったゴメスは、辰次郎に５才の時の旅の様子を思い出させて、その秘密を探ろうとして、呼び寄せた。
ゴメスのもとで、下働きとして生活しはじめた辰次郎だが、昔の記憶はなかなか浮かび上がらない。彼が生まれた村へ連れていかれ、当時一緒に遊んだ幼馴染みを思い出したことがきっかけで、次第に記憶がよみがえる。友達と隣の村まで遊びにいって、独り暮らしのよそ者に飼われていた犬に出会った。その犬がくわえていた緑のプラスティック容器。それを取り上げて、中にあった白い粉末を一緒になめたことを思い出す。もしかすると、それが鬼赤痢の病原菌ではなかったか？
日本へ船出する前の養生所で、知らない男が飲ませてくれた甘い水。もしかしたら、それが治療薬ではなかったか？
犬を飼っていた男と、甘い水をくれた男は同一人か？そういえば薬主問屋で会った男にも似ている。
そんなところからゴメスの手下らと捜査をすすめていき、ついに、犯人たちを捕まえ、特効薬も見つかる。
本来、江戸を出たものは二度と戻れないのだが、余命わずかな辰次郎の父親は特別に、入国を許され、運ばれてくる。辰次郎が生まれた村に父親をつれていくと、少し顔色がよくなる。もしかして、多少は長生きできるかもしれないと思う辰次郎。
鬼赤痢の原因は、その病を研究していた病理学者が、生命兵器に利用されるのを恐れ、江戸に隠れたためだった。病原菌を始末するつもりで、惜しくなり、一部を江戸に持ち込んでしまう。土中に埋めたそれを、犬がほじくりだし、それを食した辰次郎と仲間たちが罹患した。
それを知った悪人が悪事に利用しようとして、新たな病が発生したのだった。