Le thème aurait été développé alors que Lionel Hampton faisait partie du groupe Benny Goodman. Un concert en 1939 oblige le groupe à voler de Los Angeles à Atlantic City ; c'est la première fois qu'Hampton prend l'avion. Il commence à siffler une mélodie en attendant que l'avion roule. Goodman lui demande ce que c'est et Hampton répond : « Je ne sais pas. Nous pouvons appeler cela Flying Home, je suppose ». Hampton avouera plus tard que cette mélodie était pour lui un moyen de ne pas penser au vol imminent. Le Goodman Quartet interprète l'air pour la première fois ce soir-là. Plus tard cette année-là, Goodman enregistre la première version de la chanson, avec un solo mémorable du guitariste Charlie Christian. Hampton aime tellement la chanson qu'elle devient son thème signature après avoir quitté l'orchestre de Goodman[3],[4].
Flying Home est enregistrée pour la première fois par le Benny Goodman Sextet le lors d'une émission de radio au Hollywood Bowl à Los Angeles. Cet enregistrement n'est édité qu'en 1975 sur l'album Charlie Christian Live! with The Benny Goodman Sextet - 1940[6]. La première version publiée en single par Capitol Records, le , est enregistrée par le sextet le à New York[1], avec des solos de Lionel Hampton au vibraphone et Charlie Christian à la guitare électrique[5]. Plusieurs autres groupes enregistrent la mélodie :
En 1942, Lionel Hampton et son orchestre enregistrent la chanson avec un solo de saxophone ténor épique d'Illinois Jacquet, alors âgé de 19 ans. La chanson devient le point culminant des spectacles live d'Hampton, Jacquet étant censé répéter son célèbre solo, note par note.
Harry James enregistre une version en 1965 sur son album New Versions of Down Beat Favorites (MGM).
Ella Fitzgerald enregistre une version de plus de 7 minutes pour l'album Digital III à Montreux (1979). Lullabies of Birdland comprend une autre version de Fitzgerald que le New York Times qualifie de « l'un des disques de jazz vocal les plus influents de la décennie… Là où d'autres chanteurs, notamment Louis Armstrong, avaient essayé une improvisation similaire, personne avant Miss Fitzgerald n'avait employé cette version. technique avec une inventivité si éblouissante[7] ».
Il existe une version de 2 min 30 s de la chanson dans le film Une équipe hors du commun de 1992 et sur la bande originale du film d'Hans Zimmer. Les interprètes ne sont pas crédités.