"French Foreign Legion" is a popular song. The music was written by Guy Wood, the lyrics by Aaron Schroeder. The song was published in 1958. It is best known in a version recorded by Frank Sinatra on 29 Dec 1958, released as a single and which appears on the albums All The Way and early UK stereo releases of Come Fly with Me.