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.
Coles was a close associate of Brenda Bufalino, who was instrumental in helping him rebuild his career in the early 1970s. Coles also had a part in the 1987 hit movie Dirty Dancing.
In 1991, Coles was awarded the National Medal of Arts by former president George H.W. Bush. Charles Honi Coles died from cancer on November 12, 1992. He was inducted, posthumously, into the Tap Dance Hall of Fame in 2003. His wife Marian Edwards Coles died on November 6, 2009. While he was performing "My One and Only" Charles had a stroke.