payne was born in ashfield, franklin county, massachusetts, on november 23, 1843, though his birth is sometimes listed incorrectly as september 23. he spent his youth in massachusetts, and attempted to enlist for the union army, but he was rejected from service due to poor health. in 1859, he was graduated from the academy of shelburne falls. in 1863, he moved to milwaukee, wisconsin, where he found work as a dry goods merchant.