The Salem area was explored by Europeans just 64 years after Jamestown was settled. Europeans settled the area in the 1700s, and Salem developed as a town serving travelers along the Great Road by 1802.

The Native American tribe which lived in the valley of the Roanoke River at the time of its first European exploration were the Totero, a friendly, Siouan-speaking group who had settled near the river. European explorers Thomas Batts and Robert Fallam, who came upon the settlement in 1671, gave the area its first recorded name - Totero Town, after the natives who lived there. The Totero's supplied Batts and Fallam with a guide to further their explorations.

As in most areas, contact with Europeans drastically changed the Native Americans' lives. While introducing new technology to the native population, European colonists also introduced diseases such as smallpox and influenza. The native populations were not immune to these new diseases and significant numbers of the native population succumbed. Those who survived often left and joined other tribes. "Not long after Batts and Fallam's expedition, the Totero moved out of the area. According to First People: The Early Indians of Virginia by Keith Egloff and Deborah Woodward, attacks by the neighboring Iroquois drove the Toteros and their allies, the Saponis, out of their villages. By the early 1700's, few Native American tribes remained in the region."

Skirmishes between settlers and Native Americans heightened during the last half of the 18th century. Fort Lewis, named in honor of Andrew Lewis, (Andrew Lewis distinguished himself in the French and Indian War, serving under George Washington in 1754 at Fort Necessity) was constructed to the west of what became Salem in 1752 in order to protect area settlers. In 1754 Lewis led Virginia troops against the Confederacy of Indian Nations in the Battle of Point Pleasant which was a precursor to the Revolutionary War. During the Revolution, Lewis drove Lord Dunmore, the last British Governor, out of Virginia.

On 15 Sep 1788, John Cole purchased from John Love, 278 acres of land on the north side of the Roanoke River. The deed identifies him as "John Cole the Blacksmith". This deed was witnessed by William Bryan Jr, his father-in-law and Samuel Cole, his brother. (Fincastle Deed, Bk. IV, pg. 51.) Fincastle Deed Book XI, pg. 482 shows sale of parcel of land by William Bryan and his wife, Patsey (widow of John Lewis son of Andrew Lewis) to John Cole Sr. This tract was formerly owned by James Bryan and was part of the Great Springs homestead of William, the immigrant. William, had transferred this portion of the homestead to son James, who sold it to William III under deed dated 1 Jan 1781(Book x, pgs. 105,106) The sale to John Cole was proven in court under a date of 12 Apr 1815. In Kegley's Virgina Frontier (p.572) , under a date of 1790,is a grant of 700 acres to James Mason and Wm. Lewis (General Lewis's son) joining the lands of John Walton and John Cole. From map in Kegley's we find that John Cole's land is shown adjoining the Bryan Great Spring Homestead on the west. Kegley's pp. 574-575, under a date of 7 Mar 1800, John Cole received a grant of 300 acres on the Roanoke from Wm. Lewis. (Recorded in Pat. Bk45, pg.237.)

In 1800, General Lewis's son William sold to his neighbor James Simpson a thirty-one acre tract of land for $100.At this time, fewer than twenty-five families inhabited the area between the Roanoke River and Fort Lewis Mountain, but Simpson subdivided the land he bought from William Lewis into purchaseable lots on each side of the area's main roadway. The first lot was purchased by Susan (also known as Susanna) Cole, daughter of Col. Phillip Cole and his wife, Susannah (Elizabeth) Egle. She paid $20 for a lot on Main Street at Cherry Alley and her lot became a landmark in Salem. Her brother Samuel also bought two lots. On 9 March 1800, Samuel also purchased 165 acres on the east side of Mason Creek which was eastward of the present town of Salem. From Fincastle land records we find that brother, John Cole, had holdings totalling 735 acres including "the old brick mansion house near Salem". The house was built prior to 1790 and family legend says that it was visited by a young Davey Crockett. Through the sale of Simpson's lots, Salem quickly grew into a prosperous community serving travelers as they headed west along the Great Road. In the first decades of the 1800's, local businesses included taverns, stables, blacksmith shops, wagon and buggy repair facilities, groceries, clothing stores, a horse racing track, and a canal navigation company.