RJ Lambert of AllMusic stated, "Mehldau’s use of modern compositional techniques brings forth some unexpected tonalities, far beyond those of melancholy. The first few variations introduce odd meters, and a spacious “American” sound reminiscent of Copland and Gershwin. The orchestration constantly shifts between smaller ensembles within the orchestra, never settling in any one texture for too long."[1] Nigel Jarrett of Jazz Journal commented, "Mehldau’s ambitious work is a theme and variations in which the neo-classicism of Stravinsky is sometimes invoked as well as the lush and sometimes wild sonorities of a full orchestra. When composers have an orchestra to write for as a rare event it’s tempting for them to get their moneysworth. Not that Mehldau over-indulges himself; in fact, he is often sparing in treating the two-part, three-to-the-bar theme to 11 variants – more if a cadenza and postlude are included and, on the album, an encore of two more variations."[3] John Garratt of PopMatters added, "The truly great thing about Variations on a Melancholy Theme is that it rewards casual as well as careful listening. If you can pinpoint the theme emerging from each variation, great. If not, it hardly matters. No matter your level of education or musicianship, Variations on a Melancholy Theme is still a treat to hear, from top to bottom. To have Mehldau release such top-tier material after 27 years of recording, the deal is only sweetened."[3]
[1]
[2]