Den første mere eller mindre permanente bosættelse i det nuværende New Madrid blev etableret af grupper af Shawnee, Delaware, Creek og Cherokee, som var blevet til flygtninge på grund af den amerikanske uafhængighedskrig. Disse flygtninge-amerikanske indianerbande accepterede spanske tilbud om at bosætte sig på Mississippiflodens vestlige bred i begyndelsen af 1780’erne. Disse blandede indianske grupper etablerede en bosættelse og en uformel handelspost, hvor en nordlig hestesko-bøjning af Mississippi mødte Chepusa-bækken, hvilket gav et let sted for landing af både. Indfødte amerikanske jægere og europæisk-amerikanske købmænd gjorde bosættelsen til et sted, hvor man kunne forarbejde jagtbyttet, herunder det værdifulde, men snavsede fedt fra bjørne og bøfler, som blev brugt til at fremstille skind og pelse. Bopladsen fik hurtigt navnet L’Anse a la Graise – “Cove of Grease” eller “Greasy Cove” (fedtbugten).
Europæisk-amerikanerne omdøbte bosættelsen til New Madrid omkring 1780 under ledelse af den spanske guvernør Bernardo de Gálvez, der var blevet udpeget til at styre det spanske Louisiana (landet vest for Mississippi-floden), og Manuel Pérez, der var viceguvernør for det øvre Louisiana i Saint Louis. De bød bosættere fra USA velkommen, men krævede, at de skulle blive spanske statsborgere. Desuden skulle de acceptere at leve under ledelse af hans udpegede empresario, oberst George Morgan, en veteran fra den amerikanske revolutionskrig fra New Jersey. Morgan rekrutterede en række amerikanske familier til at bosætte sig i New Madrid, hvilket tiltrak et par hundrede mennesker til regionen. Bosætningen i 1790’erne og begyndelsen af 1800-tallet forblev relativt lav på grund af den fysiske geografi i New Madrid og dets opland. Mississippi skyllede ofte byens flodbredder væk, og et spansk fort blev skyllet væk. New Madrid var omgivet af lavt, sumpet land og udviklede et velfortjent ry for sygdomme, især om sommeren og efteråret. Spanske folketællinger foretaget i slutningen af 1790’erne registrerede omkring 800 indbyggere i landsbyen New Madrid. New Madrid fortsatte med at fungere som et sted for udveksling mellem de indfødte amerikanere i St. Francis-flodens dal og de europæiske amerikanske handelsmænd, der opererede fra New Madrid.
I 1800 byttede Spanien territoriet tilbage til Frankrig i den tredje San Ildefonso-traktat. Efter at have forsøgt at genvinde kontrollen med Saint-Domingue (det nuværende Haiti), hvor et slaveoprør var i gang, opgav Napoleon sine nordamerikanske kolonier og gik med til at sælge dette område til USA i 1803 som en del af Louisianakøbet.
Området er kendt som stedet for en række af mere end 1.000 jordskælv i 1811 og 1812, der varierede op til ca. styrke 8, det kraftigste jordskælv uden for subduktionszonen, der nogensinde er registreret i USA. New Madrid ligger langt fra nogen pladegrænser, men det ligger i den seismiske zone New Madrid. Det store jordskælv kunne mærkes så langt væk som til østkysten.
Under borgerkrigen fandt slaget ved Island Number Ten sted på Mississippi-floden nær New Madrid.
I antebellum-perioden blev dette frugtbare oversvømmelsesområde udviklet til bomuldsplantager, baseret på slavebundne afroamerikaneres arbejdskraft. De blev frigjort efter borgerkrigen og arbejdede for at skabe sig et nyt liv. Da de hvide kæmpede for at genetablere deres dominans efter rekonstruktionstiden, intimiderede og angreb de sorte under dække af Jim Crow-lovgivningen og forsøgte at undertrykke stemmerettigheder og kontrollere deres aktiviteter. Det er dokumenteret, at tre afroamerikanske mænd blev lynchet af hvide i New Madrid, amtsbyen, omkring århundredeskiftet: Ukendt neger den 29. november 1898; Louis Wright, en musiker i et minstrel-show, der blev anklaget for skænderier med hvide, blev hængt den 17. februar 1902; og ukendt neger den 30. maj 1910.
Med begyndelsen af det 20. århundrede var der ved at blive udviklet en vis industri i New Madrid, som havde to tømmermøller, en kornkværn, en stav- og hovedfabrik og en bomuldscentrifuge. Den blev betragtet som en rå by. Der var fire protestantiske kirker, to med uafhængige afroamerikanske menigheder, og en katolsk kirke. I 1900 boede der 1.489 mennesker i New Madrid; i 1910 var der 1.882 indbyggere.