Leatherwood's career began in territory bands around Texas, including the Mustang Band. Late in the 1930s he worked with Joe Venuti, and in the following decade played in Bob Chester's and Tommy Dorsey's bands. During World War II he played in military bands in California, then played with Les Brown from 1947 into the next decade.
He worked extensively as a freelance studio musician in the 1950s and 1960s, primarily in jazz and pop music. He appeared on record with Doris Day, Rosemary Clooney, Julie London (including on the hit song "Cry Me a River"), and Sonny James. Late in his life he played with Dick Cary's Tuesday Night Friends. He appeared on over 120 recordings in the genre of jazz alone.