ハバナのタクシー運転手バルバロは音楽業界に進出する夢を持っていた。そんな折、彼は「ブエナ・ビスタ・ソシアル・クラブ」のスター、ピオ・レイバと出会う。ピオをマエストロに迎えて若手ミュージシャンによるバンドを組みたいというバルバロ。最初は興味を示さなかったピオだが美しい女性シンガー、オスダルヒアとの出会いによって乗り気になった。バルバロとピオはハバナの隅々にまで足を運び、有能なミュージシャンたちをスカウトしていく。全てが順調に進んでいった。バルバロの夢はキューバから遠く離れた異国で自分のバンドのコンサートを開くことだった。タクシーでバンドの音楽をかけていると、ある日乗ってきた日本人観光客が興味を示してきた。この運命の出会いから間もなくして、バンドは東京行きの飛行機の中に座ることになる。ハバナとは対極にある東京で、メンバーは、音楽に国境は無いことを実感するのだった。熱狂的に彼らを迎え入れる東京の観客たち。そしてここにバンド「ザ・サンズ・オブ・キューバ」が誕生したのだ……。