Named after Nuevo Madrid, a district located in the region, the area was under Spanish rule following France's cession of Louisiana after being defeated in the Seven Years' War.

French Canadians from New France landed in this area in 1781 and established the first European settlement in the present county at New Madrid along the Mississippi River.

The Spanish governor, Bernardo de Gálvez, appointed American colonel William Morgan, a Revolutionary War veteran from New Jersey, as empresario to recruit new settlers for the area.

After failing to regain control of its colony of Saint-Domingue, where a slave rebellion had been raging, France gave up on North America, selling its large territory west of the Mississippi River in 1803 to the United States under the Louisiana Purchase.

[5] In the floodplain of the Mississippi, this area was long cultivated by planters using enslaved African Americans for cotton production.

A request dated January 13, 1814, by the Territorial Governor William Clark, asked for federal relief for the "inhabitants of New Madrid County.

"[citation needed] The county had its peak of population in 1940, according to US census records, as shown in the table.

Scientists expect that eventually the river will cut a new channel across the narrow neck of the peninsula, which will gradually be attached by infill land to Missouri.

The most predominant denominations among residents in New Madrid County who adhere to a religion are Southern Baptists (62.86%), Roman Catholics (8.80%), and Methodists (7.36%).

Smith won a special election on Tuesday, June 4, 2013, to finish out the remaining term of U.S. Representative Jo Ann Emerson (R-Cape Girardeau).

New Madrid County, along with the rest of the state of Missouri, is represented in the U.S. Senate by Josh Hawley (R-Columbia) and Roy Blunt (R-Strafford).

At the presidential level, New Madrid County, lying in the Missouri Bootheel (one of the regions of Missouri most closely associated with the American South), was powerfully Democratic from shortly after the Civil War through 2000; from 1868 through 2000, it voted Republican only in Harding's, Hoover's, Nixon's, and Reagan's national landslides in 1920, 1928, 1972, and 1984, respectively.

Voters in New Madrid County generally adhere to socially and culturally conservative principles but are more moderate or populist on economic issues, typical of the Dixiecrat philosophy.

In the 2008 presidential primary, voters in New Madrid County from both political parties supported candidates who finished in second place in the state at large and nationally.

Senator Hillary Clinton (D-New York) received more votes, a total of 1,801, than any candidate from either party in New Madrid County during the 2008 presidential primary.