Haynes was a native of West Hartford, Connecticut, and was the son of an African American man and a white woman. He spent much of his childhood as an indentured servant in the house of a Granville, Massachusetts farmer. A regular churchgoer, he began to preach as a boy. He served in the militia during the American Revolution, including garrison duty at the recently captured Fort Ticonderoga in 1776. Haynes also became an anti-slavery activist. In addition to arguing against involuntary servitude and preaching against the slave trade, Haynes also advocated against the colonization movement, arguing that people of African descent living in the United States should be entitled to the same rights as other citizens, and that having them resettle in Africa would not be beneficial.