1970年8月23日フロリダ州マイアミで生まれる。
本格的なクラシック・ピアノの教育を6歳からを受け、14歳でジャズ・ピアノに傾倒する。
高校時代は、バークリー音楽大学主催のコンペティションで「最優秀オール・アラウンド・ミュージシャン賞」を受賞する。高校卒業後'89年にニューヨークに進出し、ジャズの道に進むため、と、フレッド・ハーシュやジミー・コブに師事する。
ニューヨークのクラブを拠点に、たちまち頭角を現すと、94年にはジョシュア・レッドマン・カルテット『ムード・スウィング』のセッションに抜擢され、一躍世界中の注目を浴びる。そこでの演奏が認められワーナー・ブラザーズと契約し、95年にメジャー・デビュー作『イントロデューシング・ブラッド・メルドー』を発表し、“同年の最優秀ジャズ・アルバムの一つ（ワシントン・ポスト紙）”と賛辞を浴びた。
デビュー作の録音に前後して、ラリー・グレナディアとホルヘ・ロッシィとレギュラー・トリオを組み、「アート・オブ・ザ・トリオ」と冠したシリーズ作品を5枚リリース。ジャズ雑誌の読者投票や批評家投票で最優秀に選ばれたほか、シリーズ2作目と4作目は、グラミー賞にノミネートされるという快挙を成し遂げた。ピアノ・ソロの作品も同時進行で発表しており、“哀歌”を主題にした『エレゲイア・サイクル』（99年）と、東京すみだトリフォニーホールで収録された『ライブ・イン・トーキョー』（04年）がある。
また、ロックとジャズのスピリットが融合した実験的作品『ラーゴ』、作曲された場所の名前が全曲につけられた『プレイシズ』などコンセプト・アルバムも制作している。
05年11月にリリースされた「デイ・イズ・ダン」（通算13作目）で、ロックのようなビート、現代クラシック音楽、スイングなど様々なスタイルを取り入れた意欲作。自己のアルバム以外では、チャーリー・ヘイデン、リー・コニッツ、ウェイン・ショーター、ジョン・スコフィールド、チャールズ・ロイドなどトップ・ミュージシャンたちとの共演も多い。彼のレコーディング活動はジャズ界にとどまらず、カントリー・ミュージック界の大御所、ウィリー・ネルソンやシンガー・ソング・ライター、ジョー・ヘンリーの作品にも参加。
また、メルドーの音楽はスタンリー・キューブリック監督の「アイズ・ワイド・シャット」、ヴィム・ヴェンダース監督の「ミリオンダラー・ホテル」を含め、数々の映画音楽にも起用された。フランス映画「僕の妻はシャルロット・ゲンズブール」のオリジナル・サウンドトラックも手掛けた。
05年にはカーネギーホールでソプラノ歌手、ルネ・フレミングと共演し、オリジナル歌曲を披露した。06年にはジャズ・シーン最大のプロジェクト＝夢の顔合わせが遂に実現！！ノンサッチ・レーベルが誇る、ジャズ界ナンバーワン・ギタリスト：パット・メセニーと、ブラッド・メルドーによるスーパー・プロジェクト第1弾として『メセニー・メルドー』をリリース。
翌07年には、『カルテット』をリリース。パット・メセニー、ブラッド・メルドー、ラリー・グレナディア、ジェフ・バラードの４名が参加し、メセニーのメロウなギターとメルドーの詩的なピアノが織り成す、鮮烈かつ繊細な、モダン・アートな仕上がりとなっている。最新作は、ニューヨークの老舗ジャズクラブ“ヴィレッジ・ヴァンガード”でライブ収録された「Live」。