謎の組織に薬を飲まされ、体が縮んでしまった有名な高校生探偵・工藤新一は、小学生の江戸川コナンと名乗りガールフレンドの蘭の家に居候している。蘭の父、毛利小五郎が探偵をしているので、情報が集めやすいと思ったからだ。

コナンの正体を知っているのは隣人の発明家・阿笠博士ただ一人。蘭たちを危険にさらさないためにも、外見が変わってしまった新一が生きていることを誰にも知られずにいる必要があるのだ。コナンはヘボ探偵の小五郎の代わりに難事件を次々と解決し、小五郎を世間に知られる名探偵に仕立て上げ、高校生の体を取り戻す情報をひたすら待っている。工藤家あての郵便物や電話は阿笠博士が管理してくれている。ある日、阿笠博士の研究室で郵便物のチェックをしていたコナンは、工藤新一あてのガーデンパーティーの招待状を見つける。差出人は有名な建築家の森谷帝ニ。興味を引かれたコナンは、新一の声で蘭に電話をかけ、コナンと小五郎と一緒にパーティーに出席するように頼み込む。蘭は承諾する代わりに、「来週の土曜日にオールナイトの映画に付き合って」と言う。来週の土曜日は都合が悪いと断ろうとするコナンだが、蘭はどうしても5月3日の夜でなくてはダメだと言い張る。強引に約束させられたコナンは大弱り。新一として蘭に会えるくらいなら、パーティーの代理を頼んだりはしないのだ。それにしても、5月3日に何があるのだ？

コナンが蘭の家に戻ると、蘭がウキウキと嬉しそうにしている。5月3日に新一とオールナイトに行って、5月4日の0時を回ったところで誕生日のプレゼントに赤いポロシャツを渡すのだと言う。映画は「赤い糸の伝説」というラブロマンス。5月は蘭も新一も赤がラッキーカラーなのだとはしゃいでいる。蘭は新一に頼まれた森谷帝ニのパーティーに小五郎とコナンを誘い、「名探偵と名建築家の出会い」とおだてられた小五郎もすっかりその気になった。

4月29日のパーティー当日、3人は壮麗な庭園と古典建築の洋館からなる森谷邸に圧倒される。森谷はイギリスの古典建築のシンメトリー（左右対称）様式に大変こだわりを持っているという。蘭とコナンは、森谷が設計した数々の建築物のパネルが飾られたギャラリーを見せてもらう。パネルの中には、先日コナンが解決した殺人事件の舞台となった黒川邸もある。森谷に新一のことを聞かれ蘭は、新一の誕生日の前夜の5月3日の夜に新一と米花シティビルで映画を見るのだと話す。米花シティビルも森谷が設計した建物だ。蘭は米花シティビルは私の自信作だと嬉しそうに語る森谷に待ち合わせの時間と場所まで教えてしまう。

5月3日。赤い服を着て、バッチリおしゃれをした蘭はウキウキと出掛けていった。新一との待ち合わせは夜の10時だ。それまでにコナンは対応策を何か講じなければならない。もっと前に断ればよかったという阿笠博士に、コナンは「毎日、嬉しそうにカレンダーに印をつける蘭を見ていたら、とても電話なんかできないよ」とこぼす。阿笠博士の発明家の腕をもってしても、新一の身代わりは作れない。大弱りのコナンが頭を抱えていると、テレビのニュースが聞こえてくる。火薬工業会社の火薬庫から、プラスチック爆弾の原料を含む大量の火薬が盗まれたという。都内各所では、同一犯人によると見られる時限発火装置を使った放火事件が続発している。森谷が設計した、あの黒川邸も被害にあっている。驚くコナン。

そこへ新一に電話がかかってくる。火薬を盗んだ犯人と名乗る男は、新一の携帯電話の番号を教えろと迫り、携帯電話を持って米花緑地公園に来いという。「急がないと、ガキどもが死ぬぞ！」と言って電話は切れた。コナンが駆けつけた公園では、光彦が元太、歩美とラジコン飛行機で遊んでいる。ラジコンから爆音を聞きつけたコナンは、空き缶を蹴り上げラジコンを空中で爆破させて事なきを得る。犯人は電話で「もう一つ爆弾が爆破する」と言ってくる。今度は米花駅の西口駅前広場だ。スケボーでダッシュするコナン。今度も間一髪で被害を防いだものの、コナンは爆風に吹き飛ばされ、意識を失って病院に担ぎ込まれる。2つの爆弾はともにプラスチック爆弾だった。目暮警部は、高校生探偵・工藤新一の評判を知って挑戦してきたか、新一に恨みを持つ人物のどちらかだろうと言う。コナンに似顔絵に描かれた犯人の顔に心当たりはない。

だが、犯人は変声器で声を変えていた。新一かコナンが知っている人物かもしれない。新一が解決した事件で一番有名なものは、西多摩市の市長を失脚させ、新しい街づくりの計画が見直しになった事件だ。この事件で身代わりの犯人だったことを新一に見破られた市長の息子が犯人なのか？その時、コナンの携帯電話が鳴り、犯人が「東都環状線に5つの爆弾を仕掛けた」と言ってくる。爆弾は午後4時を過ぎてから、電車が時速60キロ未満で走行した場合と、日没までに爆弾を取り除かなかった場合に爆発するという。もう4時を過ぎている。電車はノンストップで走らせ続けるしかない。