Bison were native to Virginia. As late as the 1730's, William Byrd II was feasting on bison when exploring his Land of Eden grant south of the Dan River. A query of the Geographic Names Information System produces a list of 79 place names in Virginia with "buffalo." (See what you get for "cow.")
The native bison may have been "wood buffalo," which could have been a different subspecies from the bison that Lewis and Clark saw on their journey up the Missouri River in 1804-6. The western bison formed large herds and migrated across vast distances in the grasslands. The Virginia bison may have migrated through Cumberland Gap to move from the Powell River valleys to the bluegrass prairies in Kentucky, but Virginia herds would have been smaller and some may have lived a relatively solitary life.
According to the Washington Post, Georgetown Farm is the "largest bison operation east of the Mississippi River."1 If you drive on Route 29, look for about 250 bison grazing on Buffalo Hill near Madison. (The other bison are raised in Free Union, further south.)