Gunnison was born in Goshen, New Hampshire, in 1812 and attended Hopkinton Academy in Hopkinton, New Hampshire. He graduated from West Point in 1837, second in his class of fifty cadets. His military career began as an artillery officer in Florida, where he spent a year in the campaign against the Seminoles. Due to his poor health he was reassigned to the Corps of Topographical Engineers the next year. Initially he explored unknown areas of Florida, searching for provision routes. However, his health soon forced him out of Florida entirely.