Born in Vienna, Barnes is the son of composer, conductor, and jazz drummer Milton Barnes and the brother of drummer Daniel Barnes. He studied voice with José Hernandez and Bill Vincent, and sang in Toronto cabarets and nightclubs during the 1980s while appearing in theatre, film, television and radio productions as an actor. He was subsequently a member of The Nylons from 1990 to 1996, and later moved to Los Angeles.
In 2003, he collaborated with the house music duo Thunderpuss on the hit dance track "Welcome to My Head", which reached number one on the Billboard club charts.
Barnes is openly gay. He was the partner of dancer and actor René Highway, who died of AIDS-related causes in 1990.