A mai New Madrid első többé-kevésbé állandó települését shawnee, delaware, Creek és Cherokee bandák alapították, akik az amerikai függetlenségi háború miatt menekültekké váltak. Ezek a menekült indián bandák az 1780-as évek elején elfogadták a spanyol ajánlatokat, hogy letelepedjenek a Mississippi nyugati partján. Ezek a vegyes indián csoportok ott létesítettek települést és informális kereskedelmi állomást, ahol a Mississippi északi, patkó alakú kanyarulata találkozott a Chepusa patakkal, ami könnyű helyet biztosított a hajók kirakodásához. Az indián vadászok és az európaiak-amerikai kereskedők a települést a vadászatok zsákmányának feldolgozására tették alkalmassá, beleértve a medvék és a bölények értékes, de piszkos zsiradékát, amelyet a bőrök és szőrmék készítéséhez használtak fel. A település hamar elnyerte a L’Anse a la Graise – “Zsíros öböl” vagy “Zsíros öböl” – nevet.
A települést az európai amerikaiak 1780 körül nevezték át New Madridra Bernardo de Gálvez spanyol kormányzó, a spanyol Louisiana (a Mississippitől nyugatra fekvő terület) kormányzásával megbízott spanyol kormányzó és Manuel Pérez, a Saint Louis-i Felső-Louisiana alkormányzója égisze alatt. Üdvözölték az Egyesült Államokból érkező telepeseket, de megkövetelték tőlük, hogy spanyol állampolgárok legyenek. Ezenkívül bele kellett egyezniük, hogy az általa kinevezett emigráns, George Morgan ezredes, egy New Jersey-i amerikai függetlenségi háborús veterán irányítása alatt éljenek. Morgan számos amerikai családot toborzott, hogy telepedjenek le New Madridban, és néhány száz embert vonzott a térségbe. A letelepedés az 1790-es években és az 1800-as évek elején New Madrid és hátországának fizikai földrajzi adottságai miatt viszonylag alacsony maradt. A Mississippi gyakran elmosta a város folyópartjait, és egy spanyol erődöt is elmosott. Az alacsony, mocsaras vidékkel körülvett New Madridban jól megérdemelt hírnevet szereztek a betegségek, különösen nyáron és ősszel. Az 1790-es évek végén végzett spanyol összeírások mintegy 800 lakost tartottak nyilván New Madridban. New Madrid továbbra is a St. Francis folyó völgyében élő indiánok és a New Madridból kiinduló európai amerikai kereskedők közötti cserekapcsolatok helyszíneként működött.
1800-ban Spanyolország a San Ildefonsói Harmadik Szerződésben visszacserélte a területet Franciaországgal. Miután megpróbálta visszaszerezni az ellenőrzést Saint-Domingue (a mai Haiti) felett, ahol rabszolgalázadás volt folyamatban, Napóleon lemondott észak-amerikai gyarmatairól, és beleegyezett, hogy ezt a területet 1803-ban eladja az Egyesült Államoknak a Louisiana Purchase részeként.
A területet 1811-ben és 1812-ben több mint 1000 földrengés sorozatának helyszíneként jegyezték fel, amelyek körülbelül 8-as erősségűek voltak, ami az Egyesült Államokban valaha feljegyzett legerősebb nem szubdukciós zónás földrengés. New Madrid messze fekszik bármelyik lemezhatártól, de a New Madrid szeizmikus zónán helyezkedik el. A nagy földrengést egészen a keleti partvidékig érezték.
A polgárháború idején a Mississippi folyón, New Madrid közelében zajlott a Tízes-szigeti csata.
A középkor előtti időszakban ezt a termékeny árteret a rabszolgasorban élő afroamerikaiak munkájára alapozva gyapotültetvények számára fejlesztették ki. A polgárháború után felszabadították őket, és új életet kezdtek dolgozni. Ahogy a fehérek a rekonstrukciós korszak után a dominancia visszaállításáért küzdöttek, megfélemlítették és megtámadták a feketéket a Jim Crow-törvények álcája alatt, a szavazati jog elfojtásán és tevékenységük ellenőrzésén munkálkodtak. Három afroamerikai férfit dokumentáltan meglincseltek a fehérek New Madridban, a megyeszékhelyen, a századforduló környékén: Ismeretlen négert 1898. november 29-én; Louis Wrightot, egy minstrel show zenészét, akit a fehérekkel való veszekedéssel vádoltak, 1902. február 17-én felakasztották; és ismeretlen négert 1910. május 30-án.
A 20. század fordulójára némi ipar fejlődött New Madridban, ahol két fűrészmalom, egy őrlőmalom, egy vessző- és fejgyár, valamint egy gyapottisztító üzem működött. Durva városnak számított. Négy protestáns templom volt, kettő független afroamerikai gyülekezettel, és egy katolikus templom. 1900-ban 1489 ember élt New Madridban; 1910-ben a lakosság száma 1882 fő volt.