"Stardust" was was composed and first recorded for Gennett Records by Hoagy Carmichael's band in 1927 as a peppy jazz number. Carmichael said he was inspired by the types of improvisations made by Bix Beiderbecke. The tune at first only attracted moderate attention, mostly from fellow musicians, a few of whom (including Don Redman) recorded their own versions of Carmichael's tune.
Carmichael reworked the tune as a slow ballad in 1929, and the same year had lyrics added to it by Mitchell Parish. Carmichael wanted to make a new recording of the tune for Gennett, but the Gennett executives vetoed the idea since they already had Carmichael's earlier recording of the tune in their catalogue. Bandleader Isham Jones, however, recorded Carmichael's new arrangement of "Stardust" which became the first of many hit records of the tune. By 1932 over two dozen other bands had recorded "Stardust".
"Stardust" became a standard of the big band era, covered by almost every prominent bandleader and singer of the generation. An arrangement by Glenn Miller was very popular; versions recorded by Louis Armstrong, Frank Sinatra, and Billie Holliday are all particularly well regarded. Some critics have called "Stardust" the finest love ballad ever written. It is one of the most recorded songs of the 20th century.