A település nevét 1296-ban említik először, Dobos határjárása alkalmával. Ekkor Karász Sándor bán fiainak a birtoka. 1330-ban már két Madáról beszélnek: Nagymadáról és Miklósmadáról. Miklósmada névadóját és a település egyházát 1354-ben említik (Nicolaus f. Petri de Mada), amikor madai és pazonyi nemesek osztozkodtak rajta. Személynévi eredetű településnév, de a személynév jelentése nem ismert.

Több település olvadt a határába, ezek közül némelyik még a XVI-XVII. században is élt: Körtvélyestele (Madával, Szigetelkével, Mérgessel és Csokallyal határos telekhely, amelyet Rohodi László 10 márkáért adott el Nagysemjéni Jánosnak), Kápolna falu, amelyet 1366-ban említenek először az okmányok; még a XV. században néptelenné vált. Kápolnával együtt merült fel a XVI-XVIII. században Zeke vagy Zeöke pallaga nevű szőlőhegy. Határába olvadt Csokaly falu, melynek 1313-ban plébánosát említik, és amelyet 1371-ben Várasdobossal mondtak határosnak. Bocsó falu neve 1322-ben tűnik fel, mint a Gutkeled nembeli Pál bán fia Miklós birtoka.

1382-ben Szatmár vármegyéhez tartozott. 1386-ban a Madai család egyik ága kihalt és az általuk birtokolt Bocsó falu birtokrész a királyra szállt, amelyet Mária királyné Károlyi Lászlónak és Mihálynak, valamint Várdai Domokosnak adományozott. 1454-ben a leleszi országos levéltár egyik oklevele ”Kis-„ és „Nagy-Mada” néven említi.

A XIV. sz. közepén a madai család két ágra szakadt, a Madai és a Pazonyi ágra. 1406-ban osztották meg a rokonok egymás közt a falu belterületét; a határbeli területek osztatlanok maradtak. 1407-ben a Madai, 1454-ben a Naményi család is birtokos. A XV. század végén a Lugosy család birtokolta, akiktől hódmezővásárhelyi birtokáért cserében bedegdi Nyáry Pál özvegye szerezte meg. A XV. században a Madai család mellett birtokosok a Kereky, Vay, majd később a Békény és Kornya családok. A XVI. sz. végén a település vásártartási jogot kapott, ettől kezdve mezővárosként említik.

1772-ben birtokosai voltak: Patay Sámuel, Pogány László, Bay István, Bersenyi József, Nyiczky Ferenc, a Vay család, Szabó Pál, Járay János, Bégányi György, Apagyi Sámuel, Nagy Péter, Gróf Haller Sándorné, Hunyadi és Péchy családok. A XIX. század első felében a Bay, Uray, Somossy, Bernáth, Berzsenyi, Szemere, Szabó, Hunyady, Jármy, Csébi Pogány, Báji Patay és Péchy családoknak volt itt birtoka. Közéleti szereplésével és műveltségével tűnt ki az ekkori nemesi családok közül a Báji Patay család, ezen belül is Patay István, aki 1830-ban Szabolcs vármegye alispánja, majd Szabolcs vármegye követe lett.

1898-ban megalakult a Nyírmadai Takarékpénztár, elnöke gr. Vay Ádám, vezérigazgatója Krausz Mór. Az 1890.es évek elején a Nyírmadai Kaszinó működéséről van tudomásunk; a lakosok olvasókört tartottak fenn. Nyírmada 1967-ben közigazgatásilag Szabolcs megyéhez és a Baktalórántházi járáshoz, legutóbb a Vásárosnaményi járáshoz tartozott.