The road from Abingdon northwest to Dickensonville (now part of U.S. Route 58 Alternate) was part of the original state highway system designated in 1918,[2] as a spur of State Route 10 (now U.S. Route 11).[3] It was assigned the number State Route 106 in the 1923 renumbering, and it was extended south and southwest five miles (8 km) towards the Tennessee state line in 1925.[4] In the 1928 renumbering, the whole of SR 106 became State Route 110, and extensions added 3.12 miles (5.02 km) in 1929[5] and another 3.24 miles (5.21 km) in 1931.[6]
U.S. Route 19 was added from Abingdon northwest to Hansonville in the late 1920s.[7] Thus, SR 110 was split in the 1933 renumbering; the short piece northwest of Hansonville became part of State Route 71 (which mainly replaced State Route 107). The piece south of Abingdon became State Route 77, and, later that year, the final 0.14 miles (0.23 km) to the Tennessee state line were added.[8] In the 1940 renumbering, SR 77 was renumbered State Route 75, as Virginia expected Tennessee to renumber its State Route 44 to match, but this never happened.[9]