今でこそ海外に拠点を置く日本人アーティストも多いが、1990年代においてその数は少なかった。その中で久保田はR&Bやソウルの本場であるニューヨークで、日本向けとアメリカ向けの両方の作品作りに邁進する。当時のことを知る久保田のディレクター兼A&Rの山中幸夫氏によると、久保田は現地のエンジニアやミュージシャンらと臆せずやりとりを重ね、信頼を得、その実力を認められ制作を行っていたという。

1996年5月にはスーパーモデルとして世界的に名を馳せているナオミ・キャンベルをフィーチャーした「LA・LA・LA LOVE SONG」を発表。木村拓哉と山口智子が主演を務めた大ヒットドラマ「ロングバケーション」の主題歌として書き下ろされたこの曲は185万枚を超えるヒットを記録し、久保田の歌唱力やソングライティング力を世間にさらに知らしめた。本格的なR&Bを愛し、それを表現しながらも、ポップスメーカーとしての矜持も決して忘れない。そんな久保田のアーティストとしての才覚を感じさせる出来事だったと言える。山中氏は、「ブラックミュージックに傾倒してすごくマニアックな音楽を作っていた方は当時もいましたが、久保田さんのようにソウルを前面に押し出しつつ、大衆が聴いても楽しめる上質な音楽を目指した才能ある人は、当時はあまりいなかったと思います」「『LA・LA・LA LOVE SONG』を聴かせてもらった瞬間にイニシャル（発売時の出荷枚数）100万枚はいくだろうと思った」と振り返る。

記録的なヒットを経て発表されたアルバム「LA・LA・LA LOVE THANG」も当然のことながら注目を浴び、多くのリスナーの耳に届いた。デビュー10周年を前に新たなフェーズに突入した久保田のキャリアは一見すると順風満帆だが、山中氏いわく「日米両方にちゃんと重きを置いて活動していたとは思うんですが、なかなかアメリカの制作に関してはうまく進まないこともあったようです。アメリカペースというか、多方面で待たされる時間が多くつらいこともあるとおっしゃってました。そういう意味では大変な時期だったかもしれません」とのことで、苦労も多かったようだ。

2000年6月には約5年ぶりとなる全米2ndアルバム「Nothing But Your Love」を発表。このアルバムに収録されているタイトル曲については、ジェイディーことJ・ディラのリミックスも作られているのが特徴だ（このリミックスは2023年12月に配信スタート）。この時期はアメリカでネオソウルが一世風靡しており、久保田はそのテイストを余すことなく表現。同アルバムの発売によって、日本にネオソウルを持ち込んだ第一人者となる。成長期とも言える1996～2005年の10年の間に久保田はディスコグラフィの中からラブソングに特化した「THE BADDEST ～Only for lovers in the mood～」、1994年～2000年に発表された楽曲の中から厳選した「THE BADDEST III」という2枚のベストアルバムを発表。2004年にはゴスペラーズ、中島美嘉、Skoop On Somebody、MISIAといったアーティストたちが参加するトリビュート盤「SOUL TREE～a musical tribute to toshinobu kubota～」が発表された。そのラインナップ、各アーティストの歌声や紡ぐサウンドには、久保田へのリスペクトと愛があふれ、どの曲を聴いても味わい深い。2004年9月、久保田は全米3rdアルバム「TIME TO SHARE」をリリースする。そしてついに──少年の頃から夢中で見ていた、自身の音楽性の趣向を決定付けた、R&B歌手なら誰もが憧れるアメリカの老舗音楽番組「SOUL TRAIN」に出演。日本人ボーカリストとして初めて同番組に出演する快挙を成し遂げた。