Nordjobb startede i 1985 på initiativ af "Den nordiske økonomiske samarbejdsgruppe". Gruppens opgave var at gennemgå det økonomiske samarbejde i Norden, foreslå forskellige tiltag for at stimulere øget vækst og fremme investeringer på tværs af grænserne.
Gruppen bestod af:
- Pehr G. Gyllenhammar (formand), Volvo
- Ulf Sundqvist, Finlands Arbetarsparbank
- Percy Barnevik, ASEA
- Sören Mannheimer, Göteborgs kommun
- Tor Aakvaag, Norsk Hydro
- Tor Moursund, Kreditkassen
- Kari Kairamo, Nokia
- Poul Svanholm, De Førenede Bryggerier
- Georg Poulsen, Metallforbundet
- Erlendur Einarsson, Kooperationen
I løbet af 1985 blev Nordjobb organiseret af et konsulentfirma i Stockholm, AB Samhällsrådet. Foreningerne Norden medvirkede i fritidsaktiviteter i bl.a. Stockholm, Helsingfors og Göteborg. I alt deltog godt 1.000 unge i Nordjobb det første år. Projektet blev evalueret i efteråret 1985 og i forbindelse hermed drøftedes den fortsatte organiseringsform. Det blev besluttet, at der skulle dannes en stiftelse med Foreningerne Norden og Stiftelsen for Industriudveksling som parter og med Nordisk ministerråd som observatør i bestyrelsen. 1. december 1985 overtog Stiftelsen Nordjobb ansvaret for projektet med landsforeningerne som operatører.
I første omgang blev Nordjobb finansieret med midler indsamlet fra erhvervslivet. Hovedsageligt fra de virksomheder, der var repræsenteret i samarbejdsgruppen. Hvorefter projektet fik en mere permanent karakter, blev bidraget fra Nordisk Ministerråd øget og i 1989 blev Nordjobbstiftelsen afviklet. Nordisk Ministerråd garanterede projektets basisfinansiering, og administrationen af projektet blev overført til Foreningerne Nordens Forbund. Nordjobb modtog også fortsat bidrag fra erhvervslivet, bilaterale fonde og nationale myndigheder.
Nordjobb oprettede et nordisk sekretariat i 2003, som var placeret i Stockholm. Sekretariatet havde en overordnet projektleder og en kommunikatør. I 2004 blev sekretariatet flyttet sammen med Foreningerne Nordens Forbnud til Malmø, hvor det forblev indtil 2012, hvor det blev flyttet til København.
Nordjobb er de senere år begyndt at arbejde med en bredere forretning og mere differentieret finansiering; bl.a. har man drevet arbejdsmarkedsprojekterne Jobbresan og Nordisk Jobstart+, som har hjulpet grupper af unge, overrepræsenteret i ledighed, i arbejde. Dette er sket ud fra den definerede mission "øge mobiliteten på det nordiske arbejdsmarked".