Fort Randolph, one of the most important military outposts of the Trans-Allegheny frontier, was located on the north bank of the Kanawha River at its mouth, at Point Pleasant. The fort was constructed in 1776 under the direction of Capt. Matthew Arbuckle, the militia commander at the site, and garrisoned by a company of troops sent from Pittsburgh. It replaced Fort Blair, built in 1774 following the victory over Chief Cornstalk and the Shawnee at the Battle of Point Pleasant and torched by Indians in 1775. The stockade was named for Peyton Randolph of Williamsburg, president of the Second Continental Congress.

With the outbreak of the Revolutionary War, Cornstalk and other Ohio chiefs who had signed the Treaty of Pittsburgh in 1775 found it increasingly difficult to restrain their warriors from joining the British. When Cornstalk and Red Hawk came to Fort Randolph in November 1777 to warn Arbuckle of the disaffection of their people, they were detained by the commander. Shortly after the arrival of Cornstalk's son Elinipsico, who came in search of his father, two hunters, Hamilton and Gilmore, were attacked by Indians and Gilmore was killed and scalped. In retribution, the three Shawnees were murdered by militiamen at the fort. Gov. Patrick Henry, Col. William Fleming, and Col. William Preston sent their regrets to the Shawnee through Cornstalk's sister, Nonhelema, who was friendly to the whites and lived at the fort.

Perhaps unrelated to the murder of Cornstalk, about 300 Wyandot and Mingo Indians attacked the fort on May 16, 1778. Unable to take Fort Randolph, they proceeded up the Kanawha River toward the Greenbrier settlements. Two militia volunteers disguised as Indians, John Pryor and Philip Hammond, overtook the force and warned the settlers, who took refuge at Fort Donnally.

Fort Randolph continued to protect the frontier, and it was garrisoned continuously during the Indian Wars of the 1790s.