« Fly Me to the Moon », initialement intitulée « In Other Words », a été écrite en 1954 par Bart Howard comme une ballade de cabaret. Howard, qui travaillait alors comme accompagnateur au piano, l’a écrite en réponse à la demande de son éditeur d’avoir des paroles plus simples. La chanson a d’abord été enregistrée commercialement par Kaye Ballard en 1954, tandis qu’un enregistrement de 1954 est également attribué à Nat King Cole et au George Shearing Quintet. Circulant initialement parmi les chanteurs de cabaret et de jazz, elle est officiellement devenue connue sous le titre « Fly Me to the Moon » en 1963, après que Peggy Lee eut convaincu Howard de changer le titre.
Composée à l’origine en 3/4, la chanson présente un caractère gracieux de valse dans ses premières versions. Quincy Jones l’a ensuite réarrangée en 4/4 pour l’enregistrement de Frank Sinatra en 1964 avec Count Basie, la transformant en un arrangement de swing vif. La version de Sinatra est devenue étroitement associée aux missions Apollo et a été diffusée lors d’Apollo 10 et d’Apollo 11. Joe Harnell a également connu le succès avec une version instrumentale bossa nova en 1962, tandis que Bobby Womack a enregistré une interprétation aux influences R&B en 1968.
