Cole's first major employment in music was with the Synco Jazz Band in Ohio; this group later became McKinney's Cotton Pickers while Cole was still a member. He left the Cotton Pickers in 1926 to play under Fletcher Henderson, with whom he stayed until 1928. While with Henderson he played on recordings behind Bessie Smith. In 1928 he toured Europe with Benny Peyton. He remained in Europe for over ten years, playing in the bands of Sam Wooding and Willie Lewis, but spent most of the years 1936-1939 out of music while recovering from a prolonged illness in Paris. He returned to the United States in 1941, leading his own bands in New York and playing in a quartet with Willie "The Lion" Smith in 1947. He continued playing locally in New York through the 1950s, and also ran a record store in Harlem.