Winding was born in Aarhaus, Denmark. In 1934 his family emigrated to the United States. His career as a professional trombonist began in 1940 with Shorty Allen's band. Subsequently, he played with Sonny Dunham and Alvino Rey, until he entered the U.S. Coast Guard during World War II.
After the war, Winding joined Benny Goodman's band, and later moved on to Stan Kenton's orchestra. In 1950, at the urging of producer Ozzie Cadena, he joined forces with J.J. Johnson to produce a highly successful series of trombone duet recordings.