[3] Born in Pratt City, Alabama, Cholly began dancing in the late 1930s before his military service in 1942 during World War II.

Atkins and Coles toured extensively nationally and internationally, performing in showcases with major jazz and swing bands, including those led by Louis Armstrong, Charlie Barnet, Count Basie, Cab Calloway, and Lionel Hampton.

[4] In the mid-1950s, Cholly began teaching dance steps to the Cadillacs, Shirelles, Moonglows, Frankie Lymon & the Teenagers, Little Anthony & The Imperials, and other vocal groups.

After working as a freelance choreographer in 1962 for The Miracles, Atkins was hired by Berry Gordy to work as a Motown choreographer in 1964, and set about developing the routines that would later become the trademark moves of other Motown acts like The Supremes, The Temptations (Atkins was also featured in the video for their hit single "Lady Soul"), The Four Tops, The Marvelettes, Gladys Knight & the Pips and others.

He choreographed for non-Motown artists as well, namely the dance routines of The Cadillacs in the 1950s, and the Sylvers, as well as The O'Jays during the mid-1970s, appearing with them on an episode of Soul Train.