押井守監督による「機動警察パトレイバー　THE MOVIE」に続く劇場版第二作。竹中直人、根津甚八が声の特別出演。 ２００２年、謎の戦闘機が横浜ベイブリッジを爆破、公には自衛隊機であったと報道され、日本は緊張状態に陥る。厳戒態勢の中、警視庁特車二課の後藤は、この事件の容疑者に、１９９９年のＰＫＦで東南アジアに於いて行方不明になっている元自衛隊員、柘植を挙げて捜索を始めるが、その頃ある飛行船が首都に向かっていた。