A stable Carbon-Nano-Fiber (CNF) layer was catalytically grown on Ni foam by decomposing ethylene. Scanning electron microscopy of the cross-section of the deposited layer on Ni foam revealed the presence of two distinct carbon layers; an apparently dense layer (‘C-layer’) at the carbon–Ni interface and a CNF layer on top of that. Variation of the growth time demonstrated that both layers develop in parallel. Characterization using temperature programmed gasification in H2, Raman spectroscopy and transmission electron microscopy confirmed that both layers consists of graphene planes, which are better ordered in CNFs as compared to C-layer. The nickel surface and the attached carbon layer have similar morphological features. This may be the reason for strong adhesion of the C-layer to Ni. CNFs are strongly attached to the C-layer via roots that penetrate into the C-layer. The interconnections of the Ni surface, C-layer and CNFs induce mechanical stability. The C-layer grows continuously with time, whereas CNF growth needs typically 20 min initiation because of the need to form small Ni particles that allow CNF formation. The continuing formation of the C-layer, also after initiation of CNF growth, is thought to be responsible for the formation of CNF roots in the C-layer.