Nodarbinātības valsts dienests tika izveidots 1991. gada 17. aprīlī. Tā centri un nodaļas tika izvietoti pa visu valsti. Sistēma tika veidota elastīga, jo atkarībā no situācijas izmaiņām darba tirgū, bezdarba līmeņa izmaiņām un darbspējas vecuma iedzīvotāju skaita attiecīgajā teritorijā tika atvērti vai slēgti Nodarbinātības valsts dienesta biroji.
1999.gada sākumā Nodarbinātības valsts dienesta struktūrā ietilpa:
Nodarbinātības valsts dienesta Centrālais aparāts,
20 finansiāli pastāvīgi Nodarbinātības valsts dienesta centri,
8 Nodarbinātības valsts dienesta nodaļas,
38 Nodarbinātības valsts dienesta biroji.
BO VAS "Nodarbinātības valsts dienests" bija divu līmeņu organizācija un sastāvēja no: akciju sabiedrības pārvaldes un filiālēm, kurās, savukārt, ietilpa 28 centri un 34 sektori. Tādējādi tika aptverta visa valsts teritorija, un BO VAS "Nodarbinātības valsts dienests" pakalpojumus varēja sniegt iespējami tuvu pakalpojuma saņēmējam.
No 2007.gada 1.janvāra, apvienojot Rīgas reģionālās filiāles Ziemeļu rajona, Rīgas rajona, Kurzemes rajona un Zemgales priekšpilsētas klientu apkalpošanas centrus, tiek izveidots Centrālais klientu apkalpošanas centrs, kā rezultātā izmainās NVA struktūra - 27 filiāles, 25 sektori un 3 klientu apkalpošanas centri.
Saskaņā ar Ministru kabineta apstiprināto koncepciju „Karjeras attīstības atbalsta sistēmas pilnveidošana” un 2007.gadā 21. jūnijā apstiprinātajiem grozījumiem „Bezdarbnieku un darba meklētāju atbalsta likumā” no 2007. gada 1. septembra NVA tiek pievienota Profesionālās karjeras izvēles valsts aģentūra (PKIVA).
No 2008.gada 1.septembra NVA pārvaldes sastāvā ir 8 departamenti un 2 no departamentiem neatkarīgas nodaļas - Nodarbinātības pakalpojumu un attīstības, Juridiskais, Informācijas tehnoloģiju attīstības, Finanšu un saimnieciskā nodrošinājuma, Grāmatvedības, Personāla, Karjeras pakalpojumu un Eiropas Sociālā fonda departamenti, kā arī Sabiedrisko attiecību un Audita nodaļas. …