The catalytic dehydrogenation (DH) and oxidative dehydrogenation (ODH) of light alkanes are of significant industrial importance. In this work both carbonaceous materials deposited on VOx/Al2O3 catalysts during reaction and unsupported carbon nanofibres (CNFs) are shown to be active for the dehydrogenation of butane in the absence of gas-phase oxygen. Their activity in these reactions is shown to be dependent upon their structure, with different reaction temperatures yielding structurally different coke deposits. Terahertz time-domain spectroscopy (THz-TDS), among other techniques, has been applied to the characterisation of these deposits – the first time this technique has been employed in coke studies. TEM and other techniques show that coke encapsulates the catalyst, preventing access to VOx sites, without a loss of activity. Studies on CNFs confirm that carbonaceous materials act as catalysts in this reaction. Carbon-based catalysts represent an important new class of potential catalysts for DH and ODH reactions.