William Wallace Barbour Sheldon was born in Westport, Essex, New York on 15 May 1836 to Gideon Sheldon and Sarah Stafford.  His mothers middle initial has variously been given as H. or A. in different records.

By 1840 the family had moved to Saranac, Clinton, New York.  His mother died in about 1846 and by the 1850 census the family was scattered, the children living with various family members and his father in Brooklyn.  That year William was living with the family of Henry A. Cole, a relative of his mother.