O primeiro assentamento mais ou menos permanente na atual Nova Madrid foi estabelecido por bandas de Shawnee, Delaware, Creek, e Cherokee que foram transformados em refugiados devido à Guerra pela Independência dos EUA. Essas bandas de refugiados indígenas americanos aceitaram ofertas espanholas para se estabelecerem na margem oeste do Rio Mississippi no início da década de 1780. Esses grupos mistos de indígenas americanos estabeleceram um assentamento e um posto de comércio informal onde uma curva em ferradura do Mississippi em direção ao norte se encontrou com o riacho Chepusa, que proporcionou um local fácil para o desembarque de barcos. Caçadores nativos americanos e comerciantes europeus-americanos fizeram do assentamento um local para o processamento da recompensa das caçadas, incluindo a valiosa, mas confusa, gordura de ursos e búfalos, que era usada na preparação de peles e peles. O povoado rapidamente adquiriu o nome L’Anse a la Graise – “Enseada da Graça” ou “Enseada Engordurada”.
European Americans renomeou o povoado Nova Madrid em cerca de 1780 sob os auspícios do governador espanhol Bernardo de Gálvez, que foi nomeado para governar a Luisiana espanhola (a terra a oeste do rio Mississipi), e Manuel Pérez, Tenente Governador da Alta Luisiana em Saint Louis. Eles acolheram colonos dos Estados Unidos, mas exigiram que eles se tornassem cidadãos da Espanha. Além disso, eles tiveram que concordar em viver sob a orientação de seu empresário nomeado, o Coronel George Morgan, um veterano da Guerra Revolucionária Americana de Nova Jersey. Morgan recrutou várias famílias americanas para se estabelecerem em Nova Madri, atraindo algumas centenas de pessoas para a região. O assentamento nos anos 1790 e início do século XIX permaneceu relativamente baixo devido à geografia física de Nova Madri e seus interiores. O Mississippi frequentemente lavava as margens dos rios da cidade, e um forte espanhol era lavado. Rodeada por terras baixas e pantanosas, Nova Madrid desenvolveu uma reputação bem merecida de doenças, especialmente no Verão e no Outono. Os censos espanhóis feitos no final da década de 1790 registaram cerca de 800 residentes na aldeia de Nova Madrid. Nova Madrid continuou a funcionar como um local de intercâmbio entre nativos americanos no vale do rio St. Francis e comerciantes europeus americanos que operam a partir de Nova Madrid.
Em 1800, a Espanha trocou o território de volta à França no Terceiro Tratado de San Ildefonso. Depois de tentar recuperar o controle de Saint-Domingue (o atual Haiti), onde uma rebelião de escravos estava em curso, Napoleão desistiu de suas colônias norte-americanas, concordando em vender este território para os Estados Unidos em 1803 como parte da Compra da Louisiana.
A área é notada como o local de uma série de mais de 1.000 terremotos em 1811 e 1812, variando até aproximadamente magnitude 8, o mais poderoso terremoto da zona de não-subducção já registrado nos Estados Unidos. A Nova Madrid está longe de qualquer fronteira de placas, mas está na Nova Madrid Zona Sísmica. O maior terremoto foi sentido tão longe quanto a Costa Leste.
Durante a Guerra Civil, a Batalha da Ilha Número Dez teve lugar no Rio Mississippi, perto de Nova Madrid.
No período antebellum, esta fértil área de planície de inundação foi desenvolvida para plantações de algodão, com base no trabalho dos afro-americanos escravizados. Eles foram emancipados após a Guerra Civil e trabalharam para fazer novas vidas. Enquanto os brancos lutavam para restabelecer o domínio após a era da Reconstrução, eles intimidaram e atacaram os negros sob o disfarce das leis Jim Crow, trabalhando para suprimir o voto e controlar suas atividades. Três homens afro-americanos estão documentados como sendo linchados pelos brancos em Nova Madrid, a sede do condado, perto da virada do século: Negro desconhecido, a 29 de Novembro de 1898; Louis Wright, um músico num espectáculo de trovadores acusado de altercações com brancos, enforcado a 17 de Fevereiro de 1902; e Negro desconhecido, 30 de Maio de 1910.
Na viragem do século XX, alguma indústria estava a ser desenvolvida em Nova Madrid, que continha dois moinhos de madeira, um moinho de grist, uma aduela e uma fábrica de encabeçamento, e um gin de algodão. Era considerada uma cidade áspera. Havia quatro igrejas protestantes, duas com congregações afro-americanas independentes, e uma igreja católica. Em 1900, 1.489 pessoas viviam em Nova Madrid; em 1910, a população era de 1.882,
.