While Leyden was serving as a master sergeant in Atlantic City and rehearsing music, Glenn Miller heard Leyden perform. Miller said to him "For a Yale man, you don't play bad tenor". Miller called on Leyden in September 1943 to conduct the Moss Hart Army Air Force spectacular "Winged Victory". This was a big musical play in Broadway's Shubert Theatre with an all service band. The show started in November 1943. Leyden next requested the opportunity to arrange for Glenn Miller, and was accepted and served as one of three arrangers for Miller's Air Force Band. His first arrangement for the band was "Now I Know". Sometimes, Leyden would write more complexity into the score than was desirable. Miller told him once "Hey Norm, it was a nice try. But remember it ain't what you write, it's what you "don't" write". In 1943, Leyden composed the theme music for the wartime radio series "I Sustain the Wings" with Glenn Miller, Chummy MacGregor, and Bill Meyers. The radio program ran from 1943 to 1944. Leyden also arranged for the reorganized Glenn Miller Orchestra of Tex Beneke. In August 2000, he led the Air Force Falconaires of the Air Force Band of the Rockies in a PBS television special, "Glenn Miller's Last Flight".