Born in Philadelphia, Pennsylvania, Coles developed his high-speed rhythm tapping on the streets of his hometown. He first went to New York City as one of the Three Millers, who were known for their intricate and difficult dance steps executed on tiny platforms. He later returned to headline at the Apollo Theater.
In 1940, while dancing with Cab Calloway's band, he met and teamed with Charles "Cholly" Atkins. As Coles & Atkins, their routine opened with a fast-paced song and tap number, followed by a precision swing dance, a soft shoe, and a tap-challenge. Their partnership lasted nineteen years.