La structuration de sa pensée musicale est au service de l’expression. Ces deux aspects de la personnalité de Brad Mehldau se mêlent et s’opposent, provoquant un effet se rapprochant du chaos organisé. En parallèle de ses activités en trio et en solo, Brad Mehldau travaille avec de nombreux musiciens de jazz comme : Pat Metheny, Charlie Haden, Lee Konitz, Michael Brecker, Wayne Shorter, John Scofield et Charles Lloyd. On a pu entendre sa musique au cinéma (Eyes Wide Shut de Stanley Kubrick, The Million Dollar Hotel de Wim Wenders). Il a également composé la bande originale du film d’Yvan Attal Ma femme est une actrice. Le Carnegie Hall de New York lui a par ailleurs commandé plusieurs œuvres pour piano et voix : The Blue Estuaries, The Book of Hours : Love Poems to God ; enregistrées avec la soprano Renée Fleming, ces pièces forment l’album Love Sublime en 2006, tandis que paraît la même année House on Hill, un disque comprenant ses compositions jazz pour trio. En 2008, le Carnegie Hall lui commande un cycle de sept chansons d’amour pour la mezzo-soprano suédoise Anne Sofie von Otter, créé en 2010. Love Songs, double album dédié à ce cycle combiné à une sélection de chants français, américains, anglais et suédois, a été largement salué par la critique. En 2013, Brad Mehldau crée Variations on a Melancholy Theme, une pièce pour orchestre qu’il a interprétée aux côtés de l’Orpheus Chamber Orchestra et du Britten Sinfonia. De 2009 à 2011, Brad Mehldau a été Artiste en résidence du Wigmore Hall de Londres, organisant des cycles de concert de jazz.