En diciembre de 1927 viaja con los hermanos Scott a Nueva York y continua trabajando con ellos hasta que en el verano de 1929 se une a la orquesta del pianista Luis Russell.

[1]​ Trabaja con varias bandas de Nueva York hasta que vuelve con Luis Russell en 1931.

[1]​ Coleman regresó a Cincinnati brevemente en el verano de 1935, después se dirigió a Europa, tocando en París con el vocalista Freddy Taylor (con quien había trabajado en la banda de Lucky Millinder).

Mientras, en París, graba con el guitarrista Django Reinhardt e hizo varios sesiones bajo su propio nombre.

[2]​[1]​ Después de una estancia en El Cairo, Egipto, Coleman regresó a los EE. UU.