The first Europeans to enter what is present-day Lee County were a party of Spanish explorers, Juan de Villalobos and Francisco de Silvera, sent by Hernando de Soto in 1540, in search of gold.
The county was formed in 1793 from Russell County. It was named for Light Horse Harry Lee, the Governor of Virginia from 1791 to 1794, who was known as "Light Horse Harry" for his exploits as a leader of light troops in the American Revolutionary War. He was the father of the Confederate General Robert E. Lee. The days surrounding its founding was a tough time for Americans and Native Americans. Lee County was the final front on the Kentucky Trace this has become known as the Wilderness Road and The Trail of the Lonesome Pine. During the 1780s and 90s Forts or Stations were put into place to aid in protecting travelers seeking to follow in Daniel Boone's footsteps to the new Kentucky Territory. Stations (or Forts) during that time were: Far Eastern Lee County Yoakum Station, present day Dryden, Va, westward to Powell River and Station Creek Rocky Station, then to Mump's Fort present day Jonesville, Va, Prist Station, Chadwell Station present day Chadwell Gap, Va, Martin's Station present day Rose Hill, Va, Owen Station present day Ewing, Va, then lastly Gibson Station which still holds its name.
Among the largest early landowners in the county was Revolutionary War officer and explorer Joseph Martin, for whom Martin's Station and Martin's Creek at Rose Hill are named, and who was awarded some in the county, which he later sold. Martin was among the earliest explorers of the region.
In 1814, parts of Lee County, Russell County, and Washington County were combined to form Scott County. In 1856, parts of Lee County, Russell County, and Scott County were combined to form Wise County, Virginia.