Lavalle was born Joseph Usifer in Beacon, New York, the son of Ralph and Jennie Usifer, both Italian immigrants. Graduating from Beacon High School, he planned to study law at Columbia University. After winning a scholarship there, Lavalle studied music at the Juilliard School and was a student of composition of Joseph Schillinger. He performed in many 1930s bands, including one in Havana, Cuba. In 1933 he became an arranger and clarinetist in the NBC house orchestra. His composition Symphonic Rhumba (1939), was broadcast by the NBC Symphony Orchestra, conducted by Leopold Stokowski, on December 6, 1942.
Lavalle worked on numerous radio programs, including The Dinah Shore Show (1939–40), The Chamber Music Society of Lower Basin Street (1940–44), Plays for Americans (1942), Highway of Melody (starring baritone Mac Morgan) with the Band of America (1944–56). On his radio shows he collaborated with Victor Borge, Mario Lanza, Robert Merrill and Dinah Shore. In November 1944, his jazz composition "Always" made it to number 29 on the top 40 charts. In 1940, The New York Times described him as "NBC's ubiquitous music maker" and said he was "of small size, dynamic, dark haired..." Lavalle told the reporter, "Music is my life, and I am happy that it is so."
Lavalle was selected over several applicants to become the conductor of the Band of America in 1948. They performed a weekly radio program on NBC Radio for eight years and almost 400 programs. Each program began with the introduction: "Forty-eight states... 48 stars... 48 men marching down the main street of everybody's hometown! Here comes the Cities Service Band of America, conducted by Paul Lavalle!"
In 1949, Lavalle and the band became one of the first musical groups to appear weekly on television.
On May 18, 1961, Paul Lavalle and the Greatest Band in America joined singer Kay Armen in a 30-minute episode of the ABC-TV series "Music For a Spring Night" entitled "Concert in the Park." The Band opened with a spirited medley ("76 Trombones," "Strike Up the Band,") and then Miss Armen took over with "I'll Be Seeing You" and other songs. Beginning in 1964, the Band of America toured extensively and also became the official band of the 1964 New York World's Fair, an engagement that lasted into 1965.