彼女が大きく飛躍したのは2004年にレーベル移籍してリリースした『Careless Love』である。プロデュースはラリー・クライン。ここで彼女がクラインと出会ったことは、その後のキャリアにとても大きなこととなった。また当時はノラ・ジョーンズが2001年にリリースした『Come Away With Me』(邦題『ノラ・ジョーンズ』)の大ヒットの余韻が尾を引いているころで、ノラの登場以降ジャズやカントリー音楽など、アメリカ合衆国のルーツ音楽のテイストを取り入れた女性シンガーが続々登場した頃でもあった。
2006年には『Half The Perfect World』をリリース。ここでマデリンはオリジナルの作曲にも参加し、シンガーとして前進したことを思わせた。特筆すべきはフランスの伝説的音楽家、セルジュ・ゲンスブールの「La Javanaise」(ラ・ジャヴァネーズ)を取り上げたことだろう。かつてはパリに住み、エディット・ピアフをデビュー作で歌っていたこともある彼女が、ゲンスブールの有名曲を取り上げたことは彼女ならではの選曲だ。またこの歌は2018年に公開された映画「シェイプ・オブ・ウォーター」で使われたのでご存知の方も多いかもしれない。
ジャズのエッセンスを内包した歌手の 代表格から新たなスタートへ
さらに、全曲オリジナルの『Bare Bones』を2008年に発表。ビルボードのジャズ・チャートで1位に輝き、彼女のシンガーとしての人気は不動のものに。続く2011年にはカサンドラ・ウィルソンとの仕事で知られるクレイグ・ストリートのプロデュースで『Standing On The Rooftop』を制作している。
その2年後の2013年、再びプロデューサーにラリー・クラインを迎えて『BlueRoom』をレコーディング。このアルバムはレイ・チャールズの1962年の名盤『Modern Sounds in Country&Western』からクラインがインスパイアされて制作されたとのこと。ここでマデリンは主にレイ・チャールズのレパートリーを歌うという新たな試みをしつつ、彼女が得意な懐かしい時代の歌を現代に蘇らせている。