By December 1929, he had left Russell (partly due to the majority of the solo work going to section mate Henry "Red" Allen), but re-joined the band on two more occasions during 1931–32.

[2] His first trip to Europe was with the band of Lucky Millinder from June until October 1933, after which he returned to New York to work with bandleaders Benny Carter and Teddy Hill, whom he recorded with in early 1935.

[2] Coleman returned to Cincinnati briefly in the summer of 1935, then headed to Europe, playing a residency in Paris with entertainer/vocalist Freddy Taylor (whom he had worked with in the Lucky Millinder band).

[2] After a sojourn to Cairo, Egypt, Coleman returned to the U.S. in March 1940, and worked throughout the 1940s with a variety of top groups including bands led by Benny Carter (1940), Teddy Wilson (1940–41), Andy Kirk (1941–42), Ellis Larkins (1943), Mary Lou Williams (1944), John Kirby (1945), Sy Oliver (1946–47), and Billy Kyle (1947–48).

[4] Like many American musicians, he felt he received the recognition he deserved from European audiences, and during the decades he lived in France he traveled and performed in clubs and concert venues all over Europe.