The future of fuel supply will undoubtedly involve the utilization of heavy crude oils, including those from nonconventional sources, such as bitumen and oil shale. Because of their dense nature and poor compositional characteristics, heavy oils cannot be admitted straightly as refinery feeds, since the direct processing of such oils hardly produces engine fuels of commercial standard. The currently available refinery setups also require substantial retrofitting in order to process such heavy feeds. Thus, heavy oils must undergo an initial upgrading called hydrotreatment (HDT) by which the feeds are converted to qualified fuel oils or synthetic crude (syncrude) for easy handling. Removing the considerable amount of sulfur (S) and nitrogen (N) compounds present in the heavy crude oils selectively by hydrodesulfurization (HDS) and hydrodenitrogenation (HDN), respectively, is among the most critical and challenging aspects of the upgrading. However, the mechanism of these two reactions, in relation to different catalytic sites, temperature, pressure, and other operation variables, is not fully understood or well-documented. By analyzing the possible reaction routes involved in S and N removal by HDT, this review sets to bridge the gap that has been left void for a long period of time, to serve as a guide for innovative heavy crude oil upgrading technologies. It finally reports the current challenges impeding the speedy inclusion of heavy crude oils into the global oil supply stream, and proffer perspective solutions together with future research trends.