It is situated within a gorge carved from the surrounding mountainous limestone terrain by Cedar Creek, a small tributary of the James River.

Consisting of horizontal limestone strata, Natural Bridge is the remains of the roof of a cave or tunnel through which the Cedar Creek once flowed.

The process of formation of the bridge is less certain, but the ideas proposed by different individuals have in common the importance of three elements: The southeast dipping of the strata, the capability of water to slowly dissolve carbonates, and the existence of numerous fractures.

Initially, the underground river started capturing water from the Poague Run about two miles (3.2 km) to the north, contributing to enlarge the incipient Cedar Creek drainage basin.

[7] In March 1742, a frontiersman named John Howard — along with his son and others — was commissioned by Governor William Gooch to explore the southwest of Virginia as far as the Mississippi River.

The party followed Cedar Creek through the Natural Bridge, then floated in buffalo-skin boats down the New, Coal, Kanawha, and Ohio rivers to the Mississippi.

[7] Thomas Jefferson purchased 157 acres (64 ha) of land including the Natural Bridge from King George III of Great Britain for 20 shillings in 1774.

Many famous guests stayed here, including John Marshall, James Monroe, Henry Clay, Sam Houston, and Martin Van Buren.

[12] In 1927 a nocturnal lighting display of the arch and gorge was designed by Samuel Hibben and Phinehas V. Stephens, illuminating engineers with the Westinghouse Company.

Visitors must purchase tickets to view the bridge from below, although the park's fees under state management are about half what had been charged under prior ownership.