Szabolcs vármegye székházának építését Nyíregyházára költözése után határozta el a megyei közgyűlés. Az épület tervezésére 1891 tavaszán Alpár Ignác budapesti műépítésszel, május végén pedig Vojtovics Bertalan és Barzó Mihály nyíregyházi építészekkel a kivitelezésre kötöttek szerződést. Még abban az évben bokrétaünnepet tartottak, a következőben pedig már a berendezésről döntöttek. A Megyeháza a kor ízlésének megfelelő eklektikus stílusban épült. A nagyterem díszítését Verán József épületszobrász, Scholtz Róbert festő és Hoyek Kálmán márványműves végezték. A kivitelezési munkákba még „belefért” a vármegyei múzeum kialakítása, valamint a homlokzat két fülkéjében álló Szabolcs vezér és Szent István király szobra is, melyek a millenniumi ünnepségek idején érkeztek meg Kallós Ede műterméből. A vármegyei hivatalok létszámának növekedése miatt az 1920-as évek végén új szárnyat építettek a Megyeházához az Egyház utcán, így alakult ki a mai zárt udvar. A teljes épületét 1983-ban kezdték el felújítani, vigyázva arra, hogy megőrizzék eredeti stílusát.