"Gravy Waltz" was composed and originally performed by Ray Brown as an instrumental in the early 1960s. Allen later set words to it, and the collaboration won the 1964 Grammy Award for Best Original Jazz Composition. Issued as an instrumental single in 1963, it hit #64 on the US Billboard charts. Though the single version was credited to "Steve Allen With Donn Trenner And His Orchestra," Allen did not play on it. As well, though Allen was credited as co-songwriter for his lyrics, the hit single version was strictly an instrumental performance.