Liquid organic chemical hydrides are effective hydrogen storage media for easy and safe transport. The chemical couple of methylcyclohexane (MCH) and toluene (TOL) has been considered one of the feasible cycles for a hydrogen carrier, but the selective dehydrogenation of MCH to TOL has been reported using only Pt-based noble metal catalysts. This study reports MCH dehydrogenation to TOL using supported NiZn as a selective, non-noble-metal catalyst. A combined experimental and computational study was conducted to provide insight into the site requirements and reaction mechanism for MCH dehydrogenation to TOL, which were compared with those for cyclohexane (CH) dehydrogenation to benzene (BZ). The kinetic measurements carried out at 300–360 °C showed an almost zero order with respect to MCH pressure in the high-pressure region (≥10 kPa) and nearly a positive half order with respective to H2 pressure (≤40 kPa). These kinetic data for the dehydrogenation reaction paradoxically indicate that hydrogenation of a strongly chemisorbed intermediate originating from TOL is the rate-determining step. Density functional theory (DFT) calculation confirms that the dehydrogenated TOL species at the aliphatic (methyl) position group (C6H5CH2) were strongly adsorbed on the surface, which must be hydrogenated to desorb as TOL. This hydrogen-assisted desorption mechanism explains the essential role of excess H2 present in the feed in maintaining the activity of the metallic surface for hydrogenation. The rate of the CH to BZ reaction was less sensitive to H2 pressure than that of MCH to TOL, which can be explained by the absence of a methyl group in the structure, which in turn reduces the binding energy of the adsorbed species. DFT suggests that the improved TOL selectivity by adding Zn to Ni was due to Zn atoms preferentially occupying low-coordination sites on the surface (the corner and edge sites), which are likely the unselective sites responsible for the C–C dissociation of the methyl group of TOL.