This area was long settled by indigenous peoples; those encountered by Europeans were of the Algonquian-speaking peoples, part of loose alliance of tribes known as the Powhatan Confederacy. The Nimcock had a village on the river where Urbanna was later developed. English settlement of the area began around 1640, with the county being officially formed in 1669 from a part of Lancaster County. This settlement pushed the Nimcock upriver. The county's only incorporated town, Urbanna, was established by the colonial Assembly in 1680 as one of 20 50-acre port towns designated for trade. It served initially as a port on the Rappahannock River for shipping agricultural products, especially the tobacco commodity crop. As the county developed, it became its commercial and governmental center.
The Rosegill Estate was developed as a plantation by Ralph Wormeley beginning in 1649, with construction of its major buildings through the 17th century. It served as the temporary seat of the colony under two royal Governors of Virginia, (Sir Henry Chicheley, who served under Thomas Culpeper, 2nd Baron Culpeper of Thoresway, and Lord Francis Howard, 5th Baron Howard of Effingham). This and other plantations in the county were developed for the commodity crop of tobacco through the 18th century, which was highly dependent on the skilled labor of enslaved African Americans.
In the 19th century, many planters from the Upper South sold slaves to the Deep South after switching from tobacco to mixed crops, which required less labor. Others migrated to the Deep South to develop new land and plantations, taking slaves with them, as did Thomas Wingfield, who moved to Wilkes County, Georgia in 1783, accompanied by 23 slaves. Following the American Civil War and emancipation, numerous freedmen stayed in the rural area of Middlesex County, working on the land for pay or a share of crops. Others moved to towns or cities as artisans, seeking more opportunities.
The Rosegill mansion continues to be used as a private residence to this day. Most of the land of the estate was purchased in the 21st century by a Northern Virginia development firm, which plans to develop it as a 700-home subdivision. An archaeological survey of the property included in the first phase of the planned development has revealed what appear to be parts of the Nimcock village. It also has uncovered evidence of the Rosegill slave community of African Americans. The developer intends to proceed with building houses over a portion of the artifacts, which will render excavation and study of them impossible.
During the American Civil War, Urbanna was planned as the point of landing for General George B. McClellan's 1862 Peninsula Campaign of 1862 to take Richmond. McClellan shifted to use Fort Monroe as the starting point, almost doubling the distance by land that troops had to travel to the Confederate citadel. Delays in reaching the gates of Richmond allowed the Confederates ample time to erect substantial defensive batteries, contributing to the Union failure in this campaign.
The Historic Middlesex County Courthouse was built in 1850-1874 by architects William R. Jones and John P. Hill. It is listed in the National Register of Historic Places. Construction of a new 21st-century county courthouse began in 2003 and was completed in 2004. It was not occupied until September 2007, however, due to a legal dispute between the county and the architect. The Historic Courthouse has been remodeled and now serves as the Board of Supervisors meeting room and the Registrar's Office.
Urbanna was incorporated on April 2, 1902, comprising an area of . The Town of Urbanna remains the county's largest commercial center and its only incorporated area. The county seat was moved to the Village of Saluda on U.S. Route 17. To the east, almost to Stingray Point, the Village of Deltaville is situated on State Route 33 between the mouths of the Rappahannock and Piankatank rivers. Once a major center for wooden boat building, the village has become known as a commercial and recreational center. Its waterfront and east to Stingray Point how has many marinas, with a concentration on Broad Creek.