The town was first settled around 1788, first by a group called the "Vermont Sufferers." These were people from land in the eastern part of New York, who had lost their claims due to land sales by Vermont for the same claims.
The town was formed in 1791 as the "Town of Jericho" in Tioga County before the formation of Chenango County. The name "Bainbridge" was adopted in 1814 in honor of United States Navy Commodore William Bainbridge. Subsequently, the town was reduced by the creation of new towns in the county: in 1793, part of Bainbridge was used to form the parts of the Towns of Norwich and Oxford; more of Bainbridge was used for the Town of Greene (1798 and 1799) and the Town of Afton (1857).