Kuwait atmospheric residue (KAR) was hydrodemetallized (HDM) over a commercial Mo/Al2O3 catalyst using a fixed-bed reactor unit. Initial coke deposition on the catalyst vs. time-on-stream (TOS) was studied by solid-state 13C NMR to derive structural information on the initial coke deposited in the first 240 h of TOS. 13C NMR spectral editing (cross-polarization technique in combination with the polarization inversion pulse sequence) was applied to distinguish on the one hand between quaternary and tertiary aromatic carbon and on the other hand between secondary and primary aliphatic carbon. Structural parameters, derived from those NMR measurements in combination with the aromaticity from single pulse excitation 13C NMR and the H/C ratio from elemental analysis, have been used to assemble the hypothetical structure of initial coke. The 1 h coke has nearly the same H/C ratio as the KAR and represents an intermediate between heavy coke generating molecules from KAR and real coke. In the following 12 h, aromatic carbon is accumulated and aromatic rings are dealkylated but the coke is still rich in hydrogen. As the carbon deposition slows down (after 50 h) further aromatic carbon is built-up and aliphatic carbon decreases. After 120 h the hydrogenation activity of the HDM catalyst is still high and prevents the coke from getting hydrogen depleted, merely the degree of alkyl-substitution has dropped compared with the start of run. With further increase of run time, carbon deposition reaches a steady state (240 h). As the analysis of a spent HDM catalyst (6500 h) from an industrial ARDS unit shows, throughout the following months of operation the porous hydrogen rich coke is increasingly converted into highly condensed polynuclear aromatic coke. THF-extraction of the used catalysts (TOS; 1, 12, 120, and 6500 h) has mainly removed small aromatic compounds with a high degree of alkyl-substitution.