Vaja (korábban Nyírvaja) város Szabolcs-Szatmár-Bereg megyében, a Mátészalkai járásban.

Neve személynévi eredetű, valószínűleg egykori tulajdonosáról kapta. Először 1272-ben említik IV. Béla király birtokadományozásakor, ekkor a név Woya és Waya alakokban fordult elő. 1312-ben már a Vay család birtokaként van említve a település. 1370 körül Vay László váradi püspök volt a tulajdonosa. A család címerét Vay Titusz kapta Zsigmond királytól hűségéért, vitézi tetteiért.

1412-ben Csernavodai István, a szomszédos Papos birtokosának jobbágyait a Vay család tagjai Vajára költöztették. 1418-ban Vajának már pallosjoga is volt.

A Vajai vár egykor terjedelmes erősség volt, a mostani épülettől kissé távolabb álló templom volt a várkápolna. A vár jelenleg fennálló épülete a réginek csupán a lakórészét képezte. A tatár invázió alatt itt húzták meg magukat a szabolcsi rendek is, és itt tárgyalták meg Rákóczival a szatmári békét.

A 16. században – házasság révén – az Ibrányiak, valamint a Jármy család is szerzett itt birtokrészt.

1578-ban Nagyvaja és Kustosvég mint két különálló falu van említve.

Az 1700-as évek végén 650 fő lakosa volt a településnek. A református gyülekezet tagjainak anyakönyvezése 1714-ben indult meg.[2]

1711-ben itt, a vajai várban találkozott II. Rákóczi Ferenc Pálffy János gróffal, a magyarországi császári csapatok főparancsnokával, néhány nappal azelőtt, hogy végleg elhagyta az országot.[3] A vajai vár urát, kuruc Vay Ádámot is bujdosásai során érte a halál. Danzigban halt meg 1719-ben. 1906-ban, Rákóczi és bujdosótársainak újratemetésekor Vay Ádám hamvait is hazaszállították, s Vaján temették el. Síremléke a református templom előtti parkban áll.

A jobbágyfelszabadításkor, 1848-ban a falu lakossága már 1002 fő volt. 1939 végén a faluból 524 fő református vajai költözött át a Baranya vármegyei Magyarbólyba. A Vay család az 1940-es évekig birtokosa maradt a településnek.

2009. július 1. óta város.