Pierwsza mniej lub bardziej stała osada na terenie dzisiejszego New Madrid została założona przez zespoły Shawnee, Delaware, Creek i Cherokee, które stały się uchodźcami z powodu wojny o niepodległość Stanów Zjednoczonych. Te uchodźcze grupy rdzennych Amerykanów przyjęły hiszpańskie oferty osiedlenia się na zachodnim brzegu rzeki Mississippi we wczesnych latach 1780-tych. Te mieszane grupy rdzennych Amerykanów założyły osadę i nieformalny punkt handlowy w miejscu, gdzie północny, podkowiasty zakręt Missisipi spotkał się z potokiem Chepusa, co zapewniło łatwe miejsce do lądowania łodzi. Rdzenni amerykańscy myśliwi i europejsko-amerykańscy kupcy sprawili, że osada stała się miejscem, w którym przetwarzano zdobycze z polowań, w tym cenny, ale nieporządany tłuszcz niedźwiedzi i bizonów, z którego przygotowywano skóry i futra. Osada szybko zyskała nazwę L’Anse a la Graise – „Cove of Grease” lub „Greasy Cove”.
Europejscy Amerykanie zmienili nazwę osady na New Madrid w około 1780 roku pod auspicjami hiszpańskiego gubernatora Bernardo de Gálvez, który został wyznaczony do rządzenia hiszpańską Luizjaną (ziemia na zachód od rzeki Missisipi), oraz Manuela Pérez, gubernatora porucznika Górnej Luizjany w Saint Louis. Przyjęli oni osadników ze Stanów Zjednoczonych, ale wymagali od nich, aby stali się obywatelami Hiszpanii. Ponadto musieli oni zgodzić się na życie pod kierownictwem wyznaczonego przez niego empresario, pułkownika George’a Morgana, weterana amerykańskiej wojny rewolucyjnej z New Jersey. Morgan zwerbował kilka amerykańskich rodzin do osiedlenia się w Nowym Madrycie, przyciągając do tego regionu kilkaset osób. W latach 90. i na początku XIX wieku osadnictwo pozostawało na stosunkowo niskim poziomie ze względu na geografię fizyczną Nowego Madrytu i jego okolic. Rzeka Missisipi często podmywała brzegi miasta, a hiszpański fort został podmyty. Otoczone niskimi, bagnistymi terenami, New Madrid zyskało zasłużoną reputację miasta chorowitego, zwłaszcza latem i jesienią. Hiszpańskie spisy ludności sporządzone pod koniec lat dziewięćdziesiątych XVII wieku odnotowały około 800 mieszkańców wioski New Madrid. New Madrid nadal funkcjonowało jako miejsce wymiany między rdzennymi Amerykanami z doliny rzeki St. Francis a europejskimi handlarzami działającymi z New Madrid.
W 1800 roku Hiszpania przehandlowała terytorium z powrotem do Francji w Trzecim Traktacie z San Ildefonso. Po próbie odzyskania kontroli nad Saint-Domingue (obecne Haiti), gdzie trwała rebelia niewolników, Napoleon zrezygnował ze swoich północnoamerykańskich kolonii, zgadzając się sprzedać to terytorium Stanom Zjednoczonym w 1803 r. jako część Zakupu Luizjany.
Obszar ten jest odnotowany jako miejsce serii ponad 1000 trzęsień ziemi w 1811 i 1812 r., o magnitudzie do ok. 8, najpotężniejszego trzęsienia ziemi w strefie nie podlegającej subdukcji, jakie kiedykolwiek zarejestrowano w Stanach Zjednoczonych. New Madrid leży daleko od jakichkolwiek granic płyt, ale znajduje się w strefie sejsmicznej New Madrid. Silne trzęsienie ziemi było odczuwalne tak daleko jak Wschodnie Wybrzeże.
Podczas wojny secesyjnej, bitwa o Wyspę Dziesięć miała miejsce na rzece Missisipi w pobliżu New Madrid.
W okresie antebellum, ten żyzny obszar zalewowy został rozwinięty dla plantacji bawełny, w oparciu o pracę zniewolonych Afroamerykanów. Zostali oni wyemancypowani po wojnie secesyjnej i pracowali, aby stworzyć nowe życie. Gdy biali walczyli o przywrócenie dominacji po okresie rekonstrukcji, zastraszali i atakowali czarnych pod przykrywką praw Jima Crowa, starając się ograniczyć głosowanie i kontrolować ich działania. Udokumentowano, że trzech Afroamerykanów zostało zlinczowanych przez białych w New Madrid, siedzibie hrabstwa, na przełomie wieków: Nieznany Murzyn, 29 listopada 1898; Louis Wright, muzyk w minstrel show oskarżony o zatargi z białymi, powieszony 17 lutego 1902; i nieznany Murzyn, 30 maja 1910.
Na przełomie XX i XXI wieku, jakiś przemysł był rozwijany w New Madrid, który zawierał dwa tartaki, młyn grist, klepkę i fabrykę nagłówków, i odziarniarkę bawełny. Miasto było uważane za surowe. Były tam cztery kościoły protestanckie, dwa z niezależnymi afroamerykańskimi kongregacjami i jeden kościół katolicki. W 1900 roku w New Madrid mieszkało 1,489 osób, w 1910 roku liczba ludności wynosiła 1,882.