Norrlandståget kördes av Statens Järnvägar fram till år 2000 då Tågkompaniet tog över. Sen körde dom fram till 2003 då Connex tog över.
Bolaget CGEA bytte år 2000 namn till Connex Transport AB. Connex ägdes av Veolia Environnement som bestämde att Veolia skulle ingå i alla företagsnamn. 2006 blev Connex
istället Veolia Transport Northern Europe AB.