Spence received little formal musical training, and led a dance band in his hometown as a teenager. He played piano and sang in his twenties, but did not publish any songs until he was almost 30 years old. For much of his career, he wrote melodies, but toward the end of the 1950s he devoted himself primarily to writing lyrics.
Among Spence's best-known songs was "Nice 'n' Easy", recorded by Frank Sinatra; Spence wrote the melody, while Alan Bergman and Marilyn Keith wrote the lyrics. The song was nominated for three Grammy awards in 1960. His tune "That Face" was first recorded by Fred Astaire in 1957, and was performed by him on Another Evening with Fred Astaire (1959); the song was later recorded by Rosemary Clooney and Barbra Streisand, among others. He also wrote the standards "Half as Lovely (Twice as True)", "If I Had Three Wishes", "Love Looks So Well on You", and "So Long My Love". Spence's songs were recorded by Dean Martin, Tony Bennett, Bobby Short, Peggy Lee, Nat King Cole, Johnny Mathis, Bing Crosby, Billy Eckstine and Dinah Shore.