The first colonists landed at Cape Henry in 1607, but it would be more than 180 years before a permanent lighthouse was erected to guide ships safely into the mouth of the Chesapeake Bay. Governor Alexander Spotswood was the first to recommend construction of a lighthouse on the site. In 1789 the First Congress of the United States enacted legislation that created the lighthouse service and gave the Cape Henry project priority status. Virginia conveyed the two-acre site to the federal government later that year, and in the spring of 1791, John McComb, Jr., best known as one of the architects of New York's City Hall (1802–1811), was awarded a contract to build the lighthouse. Based on Delaware's Cape Henlopen Lighthouse (1767; destroyed 1924), the Cape Henry Lighthouse consists of a tapered octagonal shaft of dressed stone with east- and west-facing windows. Like its predecessor in Delaware, the lighthouse was situated atop a large dune for greater visibility. McComb's contract also called for the erection of a wooden keeper's cottage and an underground oil storage vault. Despite the necessity of sinking the foundations of the lighthouse deeper than expected, work proceeded quickly, and the 92-foot-high landmark was operational by October 1792. After visiting the lighthouse in 1798, Benjamin Henry Latrobe described it as “solid,” but criticized its interior wooden staircase as a potential fire hazard.
The lighthouse guided ships past Cape Henry through most of the nineteenth century, aided by several modifications, including its lantern, lens, and a new tower shaft. Concerns first expressed in an 1872 inspection about its stability eventually led to its replacement. Between 1875 and 1881, a new 157-foot lighthouse of cast and wrought iron, containing more powerful lamps, was constructed 350 feet southeast of the original structure. Access to the old lighthouse was given to the APVA, which placed a tablet commemorating the landing of the first colonists at is base in 1896; it was deeded to the association in 1930.