戦後間もないフランス。内気で友達もできない孫のシャンピオンを不憫に思ったおばあちゃんは、ＴＶセットやピアノ、おもちゃの列車、ブルーノという名前の子犬など、色々なものを買い与えたが、シャンピオンが興味を示すものはなかった。そんなある日、おばあちゃんは、偶然シャンピオンが有名な自転車選手の写真をスクラップしていることを知り、早速三輪車をプレゼント。するとシャンピオンは、今までに見たこともないようないきいきとした顔で、嬉しそうに三輪車に夢中になっていった。そんなシャンピオンのために、おばあちゃんは来る日も来る日も厳しいトレーニングを見守り、いつしか世界最高峰の自転車競技の祭典、ツール・ド・フランスに参加するまでに育て上げる。しかし、レースの最中に思わぬ事故が起きる。首位グループから離されたシャンピオンと他の選手2名が、救護車になりすました謎のマフィアに誘拐されてしまったのだ。道路の脇にシャンピオンの自転車が乗り捨てられているのを発見したおばあちゃんは、ブルーノの嗅覚をたよりに、孫の行方を追いかけるが、シャンピオンを乗せた大きな船はすでに出航してしまったところだった。おばあちゃんは愛犬・ブルーノをパートナーに、嵐で大荒れの海を小さな足漕ぎボートでさらに追いかける。そして、摩天楼そびえ立つ“ベルヴィル”という名前の巨大都市にたどり着いた。一方、シャンピオンたちは、マフィアのボスによって賭博レース用の選手としてベルヴィルのフランス・ワイン・センター内にある違法のギャンブル場に連れてこられていた。そこでは、床に打ち付けられた自転車をこぎつづけ、棄権や負けは死を意味するという、まさに命がけのレースが行われていたのだ…。その頃、知らない街で途方に暮れるおばあちゃんとブルーノは、偶然“ベルヴィルのトリプレット”と呼ばれる老婆たちに出会う。彼女たちは昔、グラマーなルックスと素晴らしいハーモニーのパフォーマンスで有名な歌手グループだった。宿もなく、お腹も空いていたおばあちゃんとブルーノは、彼女たちの古ぼけたアパルトマンに泊めてもらうことになった。そして、チャンスはある日突然やってきた。レストランのステージで歌っていた三つ子とおばあちゃんの前に、マフィアのボスが客として現れ、ブルーノがシャンピオンの匂いを嗅ぎつけたのだ。こうして、陽気な三つ子の三姉妹を味方につけ、さらなる追跡が始まった。果たして、おばあちゃんとブルーノは、最愛の孫シャンピオンを救い出すことができるのだろうか。