Henry got his nickname by doing a dance style called 'Legomania', which made him look as if he had rubber legs which described his style of dance. Started dancing for tips at Lizzie Murphy's Sporting House singing and dancing to the blues when he was just a kid and later as a "Pick" on some Vaudeville stage shows. At age sixteen he went on the Minstrel road with Bobby Grant's Female Impersonators.

    Doing anything he could to make a name for himself and show his skills, at age sixteen he would join a traveling Minstrel show called 'Bobby Grants Female impersonators' as a dancer. While touring with this show he would enter local Cakewalk and Charleston dance contests with his own pianist Eddie Heywood Sr. where he became a champion. Henry says that "he was pretty good cakewalker who won most of the time." Later Henry put together his own vaudeville act for the T.O.B.A. circuit.

    "Rubberlegs" Williams used a variety in his acts. He combined eccentric dancing with High Kicks, Wiggles and Shimmies along with the Camel Walk, The Grind, the Boogie Woogie, The Strut and Truckin' etc. Many chorus lines of the day would also used the style of Williams.

    Williams was also a singer who became a Blues Shouter and recorded a few songs with such bands as Clyde Hart's ALL STARS and Miles Davis and supplied the vocals for Dizzy Gillespie "Hot House" on 1/4/1945 New York recordings.