Haines was born Charles William Haines on January 2, 1900 in Staunton, Virginia. He sang in the choir of Trinity Episcopal Church. He spent much time in the local movie theater. Haines ran away from home at 14 with his boyfriend. They opened a dance hall in Hopewell, Virginia. The Haines family found their son. He returned home to help support his sick father. He found his way to New York City. He joined the gay community in Greenwich Village. He did some modelling. He was discovered by a talent scout who sent him to Hollywood.