Dansk Jernbane ApS (DJ) blev stiftet i august 2004 af de Luxemburgske Statsbaner (Société Nationale des Chemins de Fer Luxembourgeois) som et søsterselskab til Norddeutsche Eisenbahngesellschaft Niebüll GmbH (NEG). Man indkøbte to tidligere DSB MY-lokomotiver fra Varde - Nørre Nebel Jernbane og påbegyndte godskørsel på NEG´s licens, idet DJ ikke selv var godkendt af de danske myndigheder. NEG havde en godslicens til kørsel vest for Storebælt og havde kørt en del tankvogne til bl.a. Grindsted.

Den 24. januar 2005 fik DJ sit sikkerhedscertifikat og kunne nu officielt stå for kørslen med hjemsted i Tønder. Man fortsatte med tankvogne til Grindsted og fik i løbet af 2005 også kørslen med det såkaldte aluminiumstog fra Grenå til Tønder. Orkanen over Danmark den 8. januar 2005 væltede millioner af træer i Jylland og resten af året kørte DJ en mængde trætog fra Herning, Skive, Aalborg, Frederikshavn mm. til Padborg til videre transport sydpå.

Af øvrige opgaver i 2005 kan nævnes transport af betonelementer til Skive Havn og ballasttog til forskellige sporombygningsarbejder. Til disse opgaver indkøbtes et tidligere DSB MX-lokomotiv fra Odsherredsbanen.

I begyndelsen af 2006 fil DJ udvidet sit sikkerhedscertifikat til også at omfatte banerne øst for Storebælt, og man overtog det såkaldte Papirtog fra Næstved til Fruens Bøge. Til disse transporter var det nødvendigt at leje yderligere maskinkraft fra Nordjyske Jernbaner. Udover papir kom transporterne i 2005 til at omfatte bl.a. ammoniaktog, måletog, limvogne til Frederikshavn og tankvogne til Koppers i Nyborg.

Ved årsskiftet 2006/07 skiftede Dansk Jernbane ApS navn til CFL Cargo Danmark ApS idet moderselskabet ønskede, at det blev mere tydeligt, hvem der stod bag selskabet. Selskabet fortsatte som sådan uændret med personale, materiel og transporter, dog nu med hjemsted i Padborg.