Under 1985 organiserades Nordjobb av ett konsultföretag i Stockholm, AB Samhällsrådet. Föreningarna Norden medverkade i fritidsverksamheten i bl.a. Stockholm, Helsingfors samt i Göteborg. Totalt deltog drygt 1 000 ungdomar i Nordjobb det första året. Projektet utvärderades på hösten 1985 och i samband med detta diskuterades den fortsatta organisationsformen. Det beslöts att en stiftelse skulle bildas med Föreningarna Norden, Nordenförbundet och Stiftelsen för industriellt utbyte som parter samt med Nordiska ministerrådet som observatör i dess styrelse.

Den 11 december 1985 övertog Stiftelsen Nordjobb ansvaret för projektet med de nationella föreningarna som operatörer. Följande år strävade direktörerna till att anknyta de självstyrande områdena direkt till stiftelsen och 1987 hade Nordjobb-utväxlingen premiär på Åland. Detta i ett viktigt samarbete med Ålands arbetsförmedlingsbyrå. Detta första år var det 17 ungdomar som arbetade på Åland och 5 unga ålänningar som var ute i Norden och jobbade. (Sedan dess har Nordjobb växt på Åland och idag har vi mellan 60 – 70 nordiska ungdomar på Åland varje sommar).

Inledningsvis finansierades Nordjobb med medel som samlats in från näringslivet, framförallt från de företag som fanns representerade i samarbetsgruppen. Vartefter som projektet fick en mer permanent karaktär ökades bidraget från Nordiska ministerrådet och 1989 avvecklades Stiftelsen Nordjobb. Nordiska ministerrådet garanterade projektets basfinansiering och förvaltningen av projektet övergick till Föreningarna Nordens förbund. Även fortsättningsvis fick Nordjobb bidrag från näringslivet, bilaterala fonder och nationella myndigheter.

Nordjobb skapade ett nordiskt sekretariat 2003 som förlades i Stockholm. Sekretariatet hade en övergripande projektchef och en informatör. År 2004 flyttades sekretariatet tillsammans med FNF till Malmö där det blev kvar till 2012 när det flyttades till Köpenhamn. 

Under senare år har Nordjobb börjat arbeta med en bredare verksamhet och mer differentierad finansiering; bl.a. har man drivit arbetsmarknadsprojekten Jobbresan och Nordisk Jobstart+ som har hjälpt grupper av ungdomar överrepresenterade i arbetslöshet i arbete. Detta har gjorts utifrån den definierade missionen ”öka rörligheten på den nordiska arbetsmarknaden”.