Den första mer eller mindre permanenta bosättningen i nuvarande New Madrid etablerades av grupper av Shawnee, Delaware, Creek och Cherokee som blev flyktingar på grund av USA:s frihetskrig. Dessa flyktingband av indianer accepterade spanska erbjudanden om att bosätta sig på Mississippiflodens västra strand i början av 1780-talet. Dessa blandade indiangrupper etablerade en bosättning och en informell handelsplats där en hästskoformad böjning av Mississippifloden mot norr mötte Chepusa creek, vilket gav en enkel plats för landstigning av båtar. Indianernas jägare och de europeisk-amerikanska handelsmännen gjorde bosättningen till en plats för bearbetning av jägarnas byten, inklusive det värdefulla men smutsiga fettet från björnar och bufflar, som användes för att tillverka skinn och pälsar. Bosättningen fick snabbt namnet L’Anse a la Graise – ”Cove of Grease” eller ”Greasy Cove”.
Européiska amerikaner döpte om bosättningen till New Madrid omkring 1780 under överinseende av den spanske guvernören Bernardo de Gálvez, som utsetts att styra spanska Louisiana (landet väster om Mississippifloden), och Manuel Pérez, guvernörsbiträde för övre Louisiana i Saint Louis. De välkomnade nybyggare från USA, men krävde att de skulle bli spanska medborgare. Dessutom var de tvungna att gå med på att leva under ledning av hans utsedda empresario, överste George Morgan, en veteran från det amerikanska revolutionskriget från New Jersey. Morgan rekryterade ett antal amerikanska familjer för att bosätta sig i New Madrid och lockade några hundra personer till regionen. Bosättningen under 1790-talet och det tidiga 1800-talet förblev relativt låg på grund av den fysiska geografin i New Madrid och dess inland. Mississippi spolade ofta bort stadens flodbanker, och ett spanskt fort spolades bort. New Madrid omges av låg, sumpig mark och utvecklade ett välförtjänt rykte om att vara sjukdomsdrabbat, särskilt under sommaren och hösten. Spanska folkräkningar som gjordes i slutet av 1790-talet registrerade omkring 800 invånare i byn New Madrid. New Madrid fortsatte att fungera som en plats för utbyte mellan indianerna i St. Francis River Valley och de europeiska amerikanska handelsmännen som opererade från New Madrid.
År 1800 bytte Spanien territoriet tillbaka till Frankrike i det tredje fördraget i San Ildefonso. Efter att ha försökt återta kontrollen över Saint-Domingue (nuvarande Haiti), där ett slavuppror pågick, gav Napoleon upp sina nordamerikanska kolonier och gick med på att sälja detta område till USA 1803 som en del av Louisianaköpet.
Området har uppmärksammats som platsen för en serie av mer än 1 000 jordbävningar 1811 och 1812, med en magnitud på upp till cirka magnitud 8, den kraftigaste jordbävning som inte är från subduktionszonen och som någonsin registrerats i USA. New Madrid ligger långt från några plattgränser, men ligger i den seismiska zonen New Madrid. Den kraftiga jordbävningen kändes så långt bort som till östkusten.
Under inbördeskriget ägde slaget vid Island Number Ten rum på Mississippifloden nära New Madrid.
Under antebellum-perioden utvecklades detta bördiga översvämningsområde för bomullsplantager, baserade på slavade afroamerikaners arbete. De frigjordes efter inbördeskriget och arbetade för att skapa sig ett nytt liv. När de vita kämpade för att återupprätta sin dominans efter rekonstruktionstiden skrämde och attackerade de svarta under täckmantel av Jim Crow-lagarna och försökte hindra dem från att rösta och kontrollera deras aktiviteter. Det finns dokumenterat att tre afroamerikanska män lynchades av vita i New Madrid, länets huvudort, vid sekelskiftet 1900: Okänd neger den 29 november 1898, Louis Wright, en musiker i en minstrel show som anklagades för bråk med vita och hängdes den 17 februari 1902, och okänd neger den 30 maj 1910.
Vid sekelskiftet 1900 utvecklades en viss industri i New Madrid, där det fanns två timmerverk, ett kvarnverk, en stav- och huvudfabrik och en bomullsrensningsanläggning. Staden ansågs vara en grov stad. Det fanns fyra protestantiska kyrkor, två med självständiga afroamerikanska församlingar, och en katolsk kyrka. År 1900 bodde 1 489 personer i New Madrid, 1910 var befolkningen 1 882 personer.