Caledonia is a town in Livingston County, New York, United States. The population was 4,255 at the 2010 census. The Town of Caledonia has the village of Caledonia. The town is in the northwest part of the county and is southwest of Rochester, New York.