Vaja (formerly Nyírvaja) is a town in Szabolcs-Szatmár-Bereg County, Mátészalka District.
His name is of personal origin, probably from his former owner. It is first mentioned in 1272 in IV. When King Bela donated his estate, the name appeared in the figures Woya and Waya. Already in 1312 the settlement was mentioned as the property of the Vay family. Around 1370, it was owned by Bishop László Vay of Oradea. The family was given the coat of arms of Vitus Titus from King Sigismund for his loyalty and heroic deeds.In 1412, the serfs of István Csernavodai, the owner of the neighboring Papos, were moved to Vaja by members of the Vay family. In 1418 Vaja already had the right of Pallos.Vaja Castle was once a large fortress, and the church was a little further away from the present building. The current building of the castle was only the living part of the old one. During the Tatar invasion, the orders of Szabolcs also established themselves here, and the peace of Satu Mare was discussed with Rákóczi.
In the 16th century, through marriage, the Ibrányians and the Jármy family also acquired a share of property here.
In 1578 Nagyvaja and Kustosvég are mentioned as two separate villages.
At the end of the 1700s, the settlement had 650 inhabitants. The registration of members of the Reformed Church began in 1714. 
Statue of Adam Vay in the statue park of the castleIn 1711, here in the castle of Vajai, II. Count Ferenc Rákóczi with Count János Pálffy, commander-in-chief of the Hungarian imperial troops, a few days before leaving the country permanently.  The lord of the castle in Butter, Adam Adam Vay, also died during his hideouts. He died in Danzig in 1719. In 1906, during the reburial of Rákóczi and his comrades-in-arms, the ashes of Ádám Vay were repatriated and Vaján was buried. Its tomb is in the park in front of the Reformed Church.
At the time of the emancipation of serfs in 1848, the population of the village was already 1,002. At the end of 1939, 524 people from the village moved to Magyarbóly in Baranya County. The Vay family remained the owner of the settlement until the 1940s.
It has been a city since July 1, 2009.