"Perdido" is a jazz standard composed by Juan Tizol and was first recorded on December 3, 1941 by Duke Ellington. However, it is their January 21, 1942, recording of the song on the Victor label, that is regarded as their original recording. In 1944, Ervin Drake and Hans Lengsfelder were enlisted to write lyrics for the tune.
The song was not usually sung with the Ellington band, the exception being Ella Fitzgerald on her 1957 album Ella Fitzgerald Sings the Duke Ellington Songbook. Later, many others recorded the song, including Sarah Vaughan, Dinah Washington, Art Tatum, Quincy Jones, the Charlie Parker Quintet, Dave Brubeck, Charles Mingus, Erroll Garner, Harry James,and "Verden Rundt's" All Star Band.
Over the years the lyrics have contained many variations, as is not unusual for songs of this era.