1959年、八大は渡辺プロからの紹介によりロカビリー映画のオーディション用にオリジナル曲を数曲作ることになった。しかし、曲は作れるものの、気軽に頼める作詞家がいない。どうしたものかと思い悩み、ひとり銀座を歩いていた八大は、日本劇場の前で見覚えのある男の姿を目にした。早稲田大学の後輩、永六輔である。オーディションの件を話すと永は快諾し、二人はその足で当時八大が住んでいた三田東急アパートヘと向かった。

夜八時から朝の六時まで、永さんは勝手に詞をつくる。僕は僕でどんどん別に作曲する。両方できたところで、明るい曲から暗い曲までズラリと並べる。そして明るい詞から暗い詞をその上に乗せてゆくんです。語呂合わせをしたり、いい詞のところを曲のいいところに乗っけてみる。そんなことをしているうちに、いいものがいくつか並び、その中に「黒い花びら」があった。（中略）この曲には、自分自身が日本人だなあと思うような、一種の怨念が入っていて、初めて歌謡曲とポピュラー音楽の匂いが調和した曲ができたのだろうと思います。

夏木陽介主演の東宝映画『青春を賭けろ』は7月28日に封切られている。本作は山下敬二郎、坂本九、清野太郎らロカビリー・スターによる青春映画で、「黒い花びら」は夏木陽介 の歌唱シーンに使われている。しかし、実際に歌っているのは、まだ無名に近い水原弘である。なお、この作品が好評だったことから8月4日公開の続編『檻の中の野郎たち』にも、八大は主題歌「練鑑ブルース」の編曲のほか幾つかの楽曲を提供している。

その「黒い花びら」が大ヒットし、創設されたばかりの第1回レコード大賞を受賞すると、永と八大は作詩・作曲のコンビとして、さらに世間の注目を集めるようになった。

そんな二人に目を付けたのがNHKテレビの末盛憲彦ディレクターである。末盛は音楽番組の企画を出し、永を構成作家、八大を音楽に起用して10月6日から『午後のおしゃべり』（火曜13:40＊20分）をスタートさせた。この番組はのちに『夢であいましょう』に発展するもので、出演は中島弘子、渥美清、黒柳徹子、三木のり平ら。中村八大モダン・トリオもレギュラー出演し、八大はブラウン管で華麗なピアノを披露することになる。

1960年3月16日から5月26日までの期間、八大は海外旅行に出掛けており、その内の20日間をニューヨークで過ごしている。そこでは本場のミュージカルやショウを見て廻り、ハーレムにあるジャズ・クラブへと通う日々が続く。深夜から明け方まで営業しているクラブの常連となり、黒人プレイヤーのなかに混じってジャム・セッションするが、そこはギャングがたむろする危険な場所であったことを後になって聞かされている。さらにクラブでは、チャールズ・ミンガスのマネージャーに“ニューヨークで働かないか”と誘われたり、前衛ジャズの旗手オーネット・コールマンのコンボともプレイしている。

帰国後、八大は創作意欲に駆られてインストゥルメンタルの作曲を始める。書き上げると同時にスタジオに入り、僅かな時間で録音を完成させた作品をアルバム『メモリーズ・オブ・リリアン』として発表。メンバーは栗田八郎(b)とジミー竹内(ds)によるトリオ編成だった。

1961年4月8日からは、いよいよ『夢であいましょう』（土曜22:00＊30分）がスタートし、忙しくも楽しい生放送が始まる。同番組は吉村祥の手になるオープニングタイトルで幕を開け中島弘子の素朴な司会、黒柳徹子の愉快なおしゃべり、渥美清や三木のり平、谷幹一らによるギャグやコント、アラン・ドロンはじめシルヴィ・ヴァルタン、トリオ・ロス・パンチョスら海外からの豪華ゲストを招くなどの様々な趣向が話題を呼んで、やがて国民的人気番組に成長していく。加えて歌と創作ダンスなどの音楽に寄り添った企画も同番組を支える重要な要素を占めていた。とりわけ“今月のうた”のために書かれた諸作品は多くの視聴者に愛唱され、大量の葉書が寄せられて番組は楽譜のプレゼントのサービスを始めている。八大は音楽監督を務めたほか、モダン・トリオを率いて出演し、時にはコメディアンさながらの愛敬をふりまいていた。

7月21日にはサンケイ・ホールにて、文化放送と渡辺プロの主催による『第3回中村八大リサイタル』が開催された。ここでは演奏と歌唱の二部形式がとられ、各々「モダンとムードの……」「彼氏と彼女が」といった副題が付けられている。第１部は八大のモダン・トリオに、福原彰(tp)、渡辺貞夫(as)、チコ菊地(ds)の3名を加えたコンボの演奏を中心とし、そこに石丸寛指揮による日本フィルハーモニー交響楽団と宮間利之とニュー・ハードが加わるといった構成だった。曲目は「ハウ・ハイ・ザ・ムーン」や「ひき潮」などのスタンダード作品を、驚くべき多彩な調性の色彩感覚と最良の編曲術で聴かせている。なお、この第１部の模様は、9月に東芝より「あなたと夜と音楽」としてレコード化された。

続く第2部では八大ゆかりの歌手やタレントが一堂に会し、夢のステージを繰り広げている。出演順に列記すると、江利チエミ、ザ・ピーナッツ　森山加代子、水原弘、山田卓、谷雅子、デューク・エイセス、石井好子、坂本九、栗林義信、古川太郎、三木のり平、水谷良重、加山雄三という豪華な顔触れで、司会は入江美樹が担当。楽曲の大半がこの公演のための書き下ろしで、坂本九が歌った「上を向いて歩こう」も、本公演で初披露された。

1962年6月26日　八大は鬼鞍順子さんと結婚した。

主人はピアノの前で作曲するわけではないんです。ピアノは殆ど使いませんでした。ときどき和音を確かめるぐらいで、あとは机に向かって五線紙に……。そのあと作曲をして出来てきますでしょ、音が。あの頃はリールのこんな大きなテープで。それを今度は自分で聴くんですね。うまくいって気に入ったりすると、何べんでも聴くんです。お酒を飲みながら、自分の曲を……。

中村順子談

一方で“サンボア”での演奏は継続的に行われていた。これは何よりも、常にピアニストでありたいという気持ちの表われで、その姿勢は終生変わることがなかった。たとえ、どんなに番組や録音の仕事が忙しくとも、夜になれぱクラブでのプレイを続けている。しかし、無理がたたって体調を崩すこともあり、その際には八大を慕う青年ピアニストが代役を務めるようになった。その青年とは、当時、ミッキー・カーチスとシティ・クローズに在籍していた鈴木邦彦である。二人の出会いは古く、ビッグ・フォアの時代に、まだ中学生だった鈴木が八大宅を訪れた頃に遡る。以来、時にはピアノを聴いてもらい、編曲の手解きを受けたりもしていたようだ。

八大先生の元へ通っていたのは、実は僕の前に三保敬太郎がいるんです。僕の慶応の先輩なんだけど、やっぱりピアニストで天才で……。彼も押し掛け弟子で、言ってみれば一番目の弟子なのかな、そういう言い方が許されるならば。三保さんと僕を弟子に……、まぁ取ったといえば取ったのかなという感じです。雑巾がけなんかやらされる（歌謡界の）内弟子ではなく、尊重してくれて、導いてくれるようなそんな兄弟のような関係でしたね。

中村八大というのは、僕にとって“あの人みたいになりたい”と思うただ一人の人。だから僕はピアノも弾いたし、編曲もしたし、作曲もしたんです。

鈴木邦彦談

やがてモダン・トリオにチコ菊地(ds)が加わってカルテットとなり、間もなく鈴木も加入した。彼はそこで八大とのピアノの連弾やピアニカ、ヴィブラフォンなどを担当している。1963年5月からは中村八大クインテットを名乗り、テレビ出演やレコード録音に加えて　全国津々浦々を巡るようになる。構成は世界のポピュラー音楽やオリジナル曲の演奏を中心に、その地に伝わる民謡までをも網羅した。例え自分が聴いたことのない曲であっても、八大は観客に最初の数章節のメロディを口ずさんでもらうだけで、即座に全パートの譜面を書き上げ、すぐさまその場で演奏している。どんな難曲であれ観客の要求に精一杯応える様は、幼き日に青島で観た恩師ダ・カール・ヘルスの、音楽に対する柔軟な姿勢からの影響だろう。

公演の空き時間や夜は常に編曲の仕事で缶詰状態となっており、その様子を側で見続けた鈴木は、それらを手伝いながら八大の音楽センスを吸収していった。

ある時、「クンちゃん（＊）、このメロディを大事にしたいんだったら、このハーモニーは変えたほうがいいと思うんだけど、このハーモニーが好きだったら、このメロディは変えたほうがいい。これとこれは一致しないよ、どっちがいい？」っていう風に、こんなペーペーの僕に対して、どっちを大事にするのか、つまり、僕の音楽性を尊重してくれたことがありましてね。もう毎晩一緒にいるわけですから、……それはもう、本当に勉強になりましたよ。

鈴木邦彦談
＊鈴木の愛称

クインテットが結成された頃、海の向こうから予期せぬビッグ・ニュースが舞い込んで来た 。坂本九の「上を向いて歩こう」が「Sukiyaki」として、アメリカの「ビルボード」「キャッシュボックス」の両誌で1位にランクされたのだ。この我が国の音楽史における、かつてない未曾有の快挙の経過を辿ってみよう。

ことの発端はイギリスのパイ・レコード社長、ルイス・ベンジャミンが1962年秋頃、プロモーションのために来日したところから始まる。彼は日本での滞在中に「上を向いて歩こう」を耳にして、坂本九のシングルを持ち帰った。イギリスでもヒットする楽曲と睨んだ彼は、ケニー・ボール＆ヒズ・ジャズメンに演奏させ、シングルとしてリリースすることを決定。その時に「Ue O Muite Arukou」では分かりづらいため、浅草で食べたすき焼きからヒントを得て「Sukiyaki」というタイトルを付けている。ケニー・ボール盤はエキゾチックなムードが受けて全英チャートの10位にランクされ、アメリカでは、その評判を聞いたキャピトル・レコードが、坂本のオリジナル盤をリリースした。すると「ビルボード」誌の1963年5月11日号で79位にチャートイン。それからは週を追う毎にランクが上がり、遂には6月15日号で1位に輝いた。その後、イギリスでもオリジナル盤がリリースされ、最終的には全英チャートの6位まで上昇、さらにはフランス、イタリア、オランダ、スペイン、ドイツはもちろんのこと、メキシコ、ブラジル、香港、インド、南アフリカほか世界30ヶ国以上でリリースされている。

こうして八大メロディは立ちどころに世界へ広まっていった。

1963年の暮れには、同年6月8日の長男力丸の誕生をきっかけに作られた「こんにちは赤ちゃん」が第5回日本レコード大賞を受賞。

翌1964年3月2日からは文化放送にて『八大朝のうた』（月曜～土曜）がスタート。この番組はゲスト歌手を迎えて1週間分を公開録音したもので、本人の書き下ろし曲やオリジナルとは異なる歌手による歌唱など、組合せの妙で多くのリスナーを惹き付けた。放送された作品のなかには未音盤化の佳曲も多く、一風変わった八大作品が楽しめる。併せて、越路吹雪や弘田三枝子などの安定した歌唱が、出勤前の会社員にその日の活力を与えていたようだ。

7月6日～7日には上野文化会館ホールにて『中村八大作品集（東京混声作曲家シリーズ No.1)』が催されている。第1部はエドガー・アラン・ポー原作の「赤い斑点」を舞台音楽化したもので、観世栄夫が演出を手掛け、第2部は谷川俊太郎が詩を提供し、松浦竹夫の演出による「我等我等（ガラガラ）」。そして第3部が「六輔・八大傑作選」と題したヒット曲集で、末盛憲彦が演出担当という構成だった。

毎週のテレビ出演にクインテットでの公演、加えて、流行歌や映画音楽の作曲、さらには舞台の編曲などで多忙な日々を送る八大は、家族とともに海外で暮らすことを考え、7月末にはニューヨークヘと移住、10月15日には長女里子が誕生している。

ニューヨーク在住のこの間、クインテットは坪井に預けるが、鈴木は自己のトリオ結成のために抜け、後任に倉本駿四郎(p)が加入、ドラムはチコ菊地から長芝正司に、ベースは永井啓二から小泉僖美雄に交代した。

いまの私の生活は、まず一週間単位のワクの中に組み立てられている。それに、演奏旅行で手いっぱいだ。そこへ、不定期の作曲の仕事をいちいちハイハイと受けていたらきりがない。といって、受ければいくらになるというミミッチイ根性がつい働く。また、受けないと仕事がまるっきりなくなるような不安感がつきまとう。

こういう生活の繰り返しを断ち切るには、どうしても一年ぐらいの留守が必要だ。それに私は、一年、二年をかけた仕事がやりたい。そういう長い時間をかけてやる仕事とはいったい何だろうと考えるのも、アメリカ行きの目的の一つであった。

とはいえ、当時の日本で最も忙しい作曲家が、それも1ドル360円の時代に1年間も海外で生活するといった発想には誰もが驚きを隠せなかった。何か裏でもあるのだろうと考えたマスコミ陣は、早速取材に駆けつけるが、八大には何の策略もなく、ただ屈託のない笑顔で自らの音楽を語るばかりだった。

そうして始まったニューヨークでの暮らしは実に快適だったようで、八大は毎日一人で舞台や映画館に出かけ　夜は生演奏が聴けるクラブに足繁く通った。当時アメリカで公開されたばかりのフランス映画『シェルブールの雨傘Les Parapluies de Cherbourg』に感銘を受け、以来、そのテーマ曲は公演の主要なレパートリーになっている。また、多くの知人がアパートを訪れており、主だったところでは、渡辺プロダクションの渡邊美佐やタレントの松島トモ子、歌手のナンシー梅木、編曲家の小野崎孝輔、そして指揮者の小沢征爾らがいたという。日本での仕事は『夢であいましょう』、NTV『明日があるさ』、そして『八大朝のうた』の譜面を送る程度に抑え、八大にとっては初めての長い充電期間となった。

1965年6月に帰国すると、再び日本での忙しい生活が始まる。しかし以前とは違い、八大には海外で培ってきた心のゆとりがあった。なおこの時期には、のちにアメリカでも発売されるアルバム『日本のメロディー』や、北島三郎との異色の顔合わせによる「帰ろかな」などを発表している。

10月17日には共立講堂にて『1st LIGHT MUSIC CONCERT中村八大と共に』が催される。このリサイタルは慶応義塾大学のアメリカ文化研究会が主催したもので、慶応大学のバンド演奏と一緒に永六輔、黒柳徹子、そして九重佑三子らが出演して学生たちの好評を得ている。

1966年1月には日生劇場で公演されたミュージカル『宝島』の音楽を担当した。この公演は石原慎太郎が『焰のカーブ』（1965年4月）に続いて発表した創作ミュージカル第2弾で、ジャニーズと梓みちよの共演が話題になっている。石原は『焰のカーブ』制作時にも八大に音楽を依頼しているが、その間八大はニューヨーク在住であったため、実現はしていない。

9月26日、次女花子誕生。

1966年10月にブラジルで開催された『第1回リオデジャネイロ国際音楽祭（ブラジル音楽祭）』に八大は江利チエミの歌唱による「私だけのあなた」を出品する。江利はヘンリー・マンシーニら各国の著名人を前に堂々と歌い上げ、類稀なる表現力で多くの観客を魅了。審査の結果、江利が最優秀歌唱賞のベスト歌唱賞、八大がオーケストラ編曲賞を受賞した。 八大は翌年の音楽祭でも坂本九の歌唱による「さよならさよなら」を出品して入賞。後年、審査員として招かれている。

この年の1月8日に『八大朝のうた』、4月2日には『夢であいましょう』が相次いで終了、時代は確実に変化していた。