The first permanent European settlement in the area was made in 1727 or 1728 by Germans from Pennsylvania. A village began to develop at the crossing of the Thornton Gap Road (US 211) and the Old Indian Road (US 11) when John Sevier established a tavern and store there in 1765. The village Sevier started continued to grow, and Sevier went on to distinction as the first governor of Tennessee. The presence of a racetrack was justification for the original name of "Cross Roads" being changed to "New Market" after a British town of the same name famous for its racetrack. One of the first publishing firms west of the Blue Ridge was formed here In 1806, existing until recent times. While prospering commercially from its location on the Valley Pike (US 11), chartered in 1834, the town also became known for its educational institutions.
In 1859 sectional tensions led to the founding of the town's own militia unit, the New Market Cavalry. This unit was mustered into Confederate service as Capt. W. H. Rice's Battery. It became part of the Second Corps, Army of Northern Virginia. The unit saw service in Jackson's 1862 Valley Campaign and all of the later campaigns in Virginia leading to Appomattox. A second local unit, the Emerald Guards, became Company E, 33d Virginia Infantry, part of the Stonewall Brigade. One of the, 33d's commanders, Col. John F. Neff, came from Rude's Hill north of New Market. Killed at Second Manassas, he is buried at Cedar Grove Cemetery, where Sigel's men rallied after the battle, 15 May 1864. Confederate troops moved in force through the town three times in Jackson's campaign of 1862. The town also was visited in 1862 by the Federals, Maj. Gen. Nathaniel Banks using the Rice House (Stanley Hall) as his headquarters. The town saw further Federal occupation in June 1864 when Hunter's force moved south to Piedmont and Lynchburg. During their brief stay, the Federals reburied their casualties from the May battle. That fall, the surrounding farms were victims of Sheridan's "burning." After the Battle of Cedar Creek, 19 October 1864, Jubal Early's forces regrouped at New Market for three weeks before probing north one final time. Major Confederate forces left the village for the last time in December 1864 when Early moved farther south into winter quarters around Waynesboro and Staunton. Ten thousand Federal cavalry, under Custer and Merritt, passed through the town in late February 1865, en route to the final battles in Virginia.
The village was the site of the earliest Memorial Day in the South, 15 May 1866.