The largely unsettled territory, traditional homeland of the now-extinct Wenrohronon Indians, was claimed by at least three territories: New York Colony, Massachusetts Bay Colony and Pennsylvania Colony up until the 18th Century.
When counties were established in New York State in 1683, the present Cattaraugus County was part of Albany County. This was an enormous county, including the northern part of New York State as well as all of the present State of Vermont and, in theory, extending westward to the Pacific Ocean. This county was reduced in size on July 3, 1766 by the creation of Cumberland County, and further on March 16, 1770 by the creation of Gloucester County, both containing territory now in Vermont.
On March 12, 1772, what was left of Albany County was split into three parts, one remaining under the name Albany County. One of the other pieces, Tryon County, contained the western portion (and thus, since no western boundary was specified, theoretically still extended west to the Pacific). The eastern boundary of Tryon County was approximately five miles west of the present city of Schenectady, and the county included the western part of the Adirondack Mountains and the area west of the West Branch of the Delaware River. The area then designated as Tryon County now includes 37 counties of New York State. The county was named for William Tryon, colonial governor of New York.
In the years prior to 1776, most of the Loyalists in Tryon County fled across the Niagara Frontier into modern day Ontario, Canada. In 1784, following the peace treaty that ended the American Revolutionary War (and a treaty with Massachusetts that finally settled who owned Western New York), the name of Tryon County was changed to Montgomery County in honor of the general, Richard Montgomery, who had captured several places in Canada and died attempting to capture the city of Quebec, replacing the name of the hated British governor.
Ontario County was split from Montgomery County in 1789 as a result of the establishment of the Morris Reserve. In turn, Genesee County was split from Ontario County in 1802 as a result of the Holland Purchase. It was not until this time that significant settlement of the territory happened. Shortly afterwards, Genesee County was made smaller in 1806, by the creation of Allegany County.
Cattaraugus County was formed in 1808, split off from Genesee County. However, at first there was no county government due to the sparse population. From 1812 to 1814, Cattaraugus County was incorporated in Allegany County; from 1814 to 1817, records of the county were divided between Belmont (Allegany County) and Buffalo (then in Niagara County). Finally, in 1817, a county government was established for Cattaraugus County.
Numerous towns in the county are named after agents of the Holland Land Company, including Ellicottville (Joseph Ellicott), Franklinville (William Temple Franklin, grandson of Benjamin Franklin), Otto and East Otto (Jacob Otto).