[3] Prior to the arrival of European settlers, the land that would become Nottoway County was inhabited by American Indians of the Nadowa tribe, an Iroquoian people.

They lived along the county's only river, the Nadowa, an Algonquian word meaning rattlesnake, and became associated with the area they inhabited.

The county contained numerous early crossroads settlements connecting the new western frontier with the population centers of Petersburg and Richmond to the north and east and until recent times owed much of its prosperity to tobacco.

First coming to Nottoway in the 1850s, railroad construction and associated industries eventually came to represent a major portion of business in the area.

[4] One of the county's larger towns, Crewe, owes its existence to the railroad siding established at Robertson's Switch in the 1880s.

In recent decades, however, the decline of tobacco, the railroads, and Fort Barfoot (formerly known as Fort Pickett), has presented the county, like much of Southside Virginia, with economic difficulties and led many Nottoway families to seek jobs and homes in Richmond and other prospering cities in central Virginia.

The county was the site of only one major skirmish, the "Battle of the Grove," which was fought near Blackstone (then known as Blacks and Whites) for control of the rail line that supplied General Robert E. Lee's Army of Northern Virginia, then entrenched around Petersburg and Richmond.

Nottoway's three towns were incorporated in the late 1800s, all along what was to become the U.S. Highway 460/Norfolk Southern Railway corridor that bisects the county.

Fort Pickett, established at the outbreak of World War II, is now headquarters of the Virginia National Guard.