Hydrodesulfurization (HDS) of straight run light gas oil (SRLGO) using novel highly active two-dimensional (2D) MoS2/graphene (G) nanohybrid catalysts is a precursor technology for the production of clean heavy fuel. The aim of this research is the synthesis of 2D MoS2/G nanohybrid catalysts by use of exfoliation method from commercial bulky MoS2 and graphite using hydrothermal ball milling system, which is a low-cost, high-yield, and scalable method. These nanohybrid catalysts were characterized by XRD, Raman spectroscopy, XPS, SEM, TEM, STEM, ICP, BET surface, TPR, and TPD techniques. Also, catalytic activities of 2D MoS2/G nanohybrid catalysts were evaluated under different operating conditions such as temperature, pressure, LHSV, and H2/Feed (SRLGO) ratio in the HDS reaction. The conversion of the HDS of SRLGO with 14000 ppm sulfur showed a considerably higher activity of 2D MoS2/G nanohybrid catalyst (99.95% HDS efficiency) compared with the Co-Mo/γAl2O3 as a commercial catalyst (90% HDS efficiency) in the operation condition (340 °C, 40 bars, LHSV: 1 h−1and H2/oil: 600 NL L−1) which is economically valuable. Using density functional theory calculations, the detailed mechanism of the HDS process over MoS2/G catalyst was explored. It was found that sulfur coverage on the Mo edge of MoS2 plays an important role in the hydrogenation of sulfur components.