Stephen was probably born in Harpswell or Islesboro, Maine, the son of Samuel Veazie of Islesboro and Phebe Holbrook. Samuel Veazie was the son of Rev. Samuel Veazie of Hull and Harpswell and Deborah Sampson.

The records for Trenton, Maine, record an intention of marriage, 4 Apr 1800, between Stephen Veazie of Islesboro and Patty Harding of Trenton. In 1800, Stephen Veazie is a resident of Islesboro, with just himself and a female in the household. See below for additional information on the name "Harding."

Stephen may be the "Stephen Phesey" in Greene Plantation, ME, in 1810 as the birthdates ranges for the family are approximately correct.

Stephen may be the 60-70 year old male in the household of Dominicus Sewell (his son-in-law) in Corinna in 1840. He does not otherwise appear in the 1840 or 1850 census records.

Between 1851 and 1852, Stephen, his sons Laban, Stephen Jr, and Alden and their families, and his daughters Martha H and Mary J and their families, all emigrated from Corinna to Caton, NY.

In a telephone conversation between Alvin John Veazie of Utah and Bruce J Veazie in Oct 2008, Alvin stated that his own middle name was John, his father's middle name was Harding and his grandfather's middle name was Reynolds. This supports the assumption that Martha, wife of Stephen, is Patty Harding of Trenton.