"Autumn Leaves" was written by Joseph Kosma, Jacques Prévert, and Johnny Mercer. It's a long story which we'll let Mark Steyn tell when he gets around to it.
Sinatra made his only studio recording of the song in 1957 for Where Are You?, one of the sad albums arranged by Gordon Jenkins. Truth to tell, I'm generally not fond of the Jenkins style. So I'm going to break my own rule here and instead of choosing a favorite recording I'm going with a video. This minimalist take, just guitar, flute, and voice, is really lovely:
I don't know where this concert took place but it's likely one from Sinatra's Word Tour for Children in 1962. Harry Klee, mentioned by Frank at the top, was a member of the sextet that accompanied Sinatra to six continents in two months. It's a shame Frank didn't sing "Autumn Leaves" in the Paris concert that was recorded and released as Sinatra and Sextet: Live in Paris, and even more of a shame that he and the sextet never got around to making a studio album of the World Tour material.