The soft (chloroform-extractable) and hard coke fractions from a suite of deactivated Co/Mo hydrodesulfurisation (HDS) catalysts with carbon contents ranging from 5 to 18% have been characterised. The hard coke accounted for between 50 and 70% of the total carbon, but was responsible for much less of a reduction in BET surface area as the carbon content increased. Indeed, significant variations in hard coke structure were revealed by solid state 13C NMR with the aromaticity ranging from 0.6 to over 0.9 with increasing carbon content and time on stream. The relatively high aliphatic contents and atomic H/C ratios for the hard cokes obtained at low levels of carbon deposition (5-7%) suggested that much of the carbon should be removed under reductive conditions. Indeed, hydropyrolysis, in which the deactivated catalysts were heated from ambient to 500°C under a hydrogen pressure of 15 MPa, removed over 90% of the carbon and recovered 70% of the BET surface that had been lost.