Ensimmäisen enemmän tai vähemmän pysyvän asutuksen nykyiseen New Madridiin perustivat shawnee-, delaware-, creek- ja cherokee-joukot, jotka joutuivat pakolaisiksi Yhdysvaltain itsenäisyyssodan vuoksi. Nämä alkuperäisamerikkalaiset pakolaisjoukot hyväksyivät espanjalaisten tarjoukset asettua Mississippi-joen länsirannalle 1780-luvun alussa. Nämä sekoittuneet intiaaniryhmät perustivat asutuksen ja epävirallisen kauppapaikan sinne, missä Mississippin pohjoiseen suuntautuva hevosenkengän muotoinen mutka yhtyi Chepusa-puroon, joka tarjosi helpon paikan veneiden maihinnousulle. Alkuperäisamerikkalaiset metsästäjät ja eurooppalaiset-amerikkalaiset kauppiaat tekivät siirtokunnasta paikan, jossa käsiteltiin metsästyssaaliita, muun muassa karhujen ja puhvelien arvokasta mutta sotkuista rasvaa, jota käytettiin nahkojen ja turkisten valmistukseen. Asutus sai nopeasti nimen L’Anse a la Graise – ”rasvalahti” tai ”rasvainen lahti”.
Eurooppalaiset amerikkalaiset nimesivät siirtokunnan uudelleen New Madridiksi noin vuonna 1780 espanjalaisen kuvernöörin Bernardo de Gálvezin, joka oli nimitetty hallitsemaan espanjalaista Louisianaa (Mississippi-joen länsipuolella olevaa maata), ja Saint Louisissa toimivan Ylä-Louisianan kuvernööriluutnantin Manuel Pérezin suojeluksessa. He toivottivat yhdysvaltalaiset uudisasukkaat tervetulleiksi, mutta edellyttivät, että heistä tuli Espanjan kansalaisia. Lisäksi heidän oli suostuttava asumaan hänen nimittämänsä empresarion, eversti George Morganin, New Jerseystä kotoisin olevan amerikkalaisen vallankumoussodan veteraanin, johdolla. Morgan värväsi useita amerikkalaisia perheitä asumaan New Madridiin ja houkutteli alueelle muutamia satoja ihmisiä. Asutus pysyi 1790-luvulla ja 1800-luvun alussa suhteellisen vähäisenä New Madridin ja sen sisämaan fyysisen maantieteen vuoksi. Mississippi huuhtoi usein kaupungin jokirantoja, ja espanjalaislinnoitus huuhtoutui pois. Matalan, soisen maan ympäröimä New Madrid sai ansaitun maineen sairauksista erityisesti kesällä ja syksyllä. Vuoden 1790-luvun lopulla tehdyissä espanjalaisissa väestönlaskennoissa New Madridin kylään kirjattiin noin 800 asukasta. New Madrid toimi edelleen St. Francis-joen laaksossa asuvien intiaanien ja New Madridista käsin toimivien eurooppalaisten amerikkalaisten kauppiaiden välisenä vaihtopaikkana.
Vuonna 1800 Espanja kauppasi alueen takaisin Ranskalle San Ildefonson kolmannessa sopimuksessa. Yritettyään saada takaisin hallintaansa Saint-Dominguen (nykyinen Haiti), jossa orjakapina oli käynnissä, Napoleon luopui Pohjois-Amerikan siirtomaistaan ja suostui myymään tämän alueen Yhdysvalloille vuonna 1803 osana Louisianan ostoa.
Alueella tapahtui vuosina 1811 ja 1812 yli 1 000 maanjäristystä, joiden voimakkuus oli noin 8 magnitudia, mikä oli voimakkain Yhdysvalloissa koskaan mitattu maanjäristys, joka ei ollut sukellusvyöhykkeellä. New Madrid sijaitsee kaukana mannerlaattojen rajoista, mutta se on New Madridin seismisellä vyöhykkeellä. Suuri maanjäristys tuntui jopa itärannikolla.
Sisällissodan aikana Mississippi-joella lähellä New Madridia käytiin Island Number Tenin taistelu.
Antebellum-kaudella tätä hedelmällistä tulva-aluetta kehitettiin puuvillaviljelmiä varten, jotka perustuivat orjuutettujen afroamerikkalaisten työvoimaan. Heidät vapautettiin sisällissodan jälkeen ja he työskentelivät luodakseen uuden elämän. Kun valkoiset pyrkivät jälleenrakennuskauden jälkeen palauttamaan valta-asemansa, he pelottelivat mustia ja hyökkäsivät heidän kimppuunsa Jim Crow -lakien varjolla ja pyrkivät estämään äänestämisen ja valvomaan heidän toimintaansa. Valkoisten on dokumentoitu lynkanneen kolme afroamerikkalaista miestä New Madridissa, piirikunnan pääkaupungissa, vuosisadan vaihteen tienoilla: Tuntematon neekeri 29. marraskuuta 1898; Louis Wright, minstrel-show’n muusikko, jota syytettiin riidoista valkoisten kanssa ja joka hirtettiin 17. helmikuuta 1902; ja tuntematon neekeri 30. toukokuuta 1910.
1900-luvun vaihteeseen mennessä New Madridissa kehitettiin jonkin verran teollisuutta, ja siellä oli kaksi sahatavaramyllyä, myllylaitos, pölkky- ja otsikkotehdas sekä puuvillatehdas. Sitä pidettiin karkeana kaupunkina. Kaupungissa oli neljä protestanttista kirkkoa, joista kahdessa oli itsenäisiä afroamerikkalaisia seurakuntia, ja yksi katolinen kirkko. Vuonna 1900 New Madridissa asui 1 489 ihmistä; vuonna 1910 väkiluku oli 1 882.