The melody of 'Autumn Leaves' was originally written as a ballet music for 'Le rendez-vous' for Roland Petit. The original stage design was done by Pablo Picasso.
Moved by the music and the dance, the French film director Michael Carné' based his screenplay on 'Le rendez-vous': not without problems. Originally he tried to talk Marlene Dietrich into playing the lead role, which she refused. Another actor refused the role because of the fact that Marlene had refused. The composer Kosma, who had set the melody of the ballet into a chanson on the poem ' Feuilles mortes' (Dead leaves), insisted in using the sung version. The movie was a disaster, but the melody (hummed by Yves Montand) became an instant hit.
History tells that the first recording was made by Cora Vaucair in 1948. Yves Montand followed the same year. In 1949, Juliette Greco made the first clip while singing the song (amidst autumn scenes of course).
The first English version, which was translated by Johnny Mercer, was sung by Edith Piaf, the famous French 'chansonier'.
The rest is history: Jo Stafford (1950), Mitch Miller (1950), Bing Crosby (1950), Artie Shaw (1951), Anny Gould (1955), Roger Williams (1955), Nat King Cole (1955), Frank Sinatra (1956), Stéphane Grapelli (1956), Duke Ellington (1957), Cannonball Adderley (1958), Sylvie Vartan (1968), Placido Domingo (1990) and Ute Lemper (1992).

Acknowledgements:
Shmoonkie Poonks, for starting my curiousity: thanks!
'The Originals' - Arnold Rypens