Hydrodeoxygenation (HDO) process is the most promising route to upgrade pyrolysis bio-oils for producing liquid transportation fuels. The catalysts used and the quality of bio-oils have played important roles for how successful such process is. This review has addressed recent advances in HDO of pyrolysis bio-oils over many different types of catalysts, concentrating on the investigations of reasons why current catalysts have showed poor stability and have hindered pyrolysis oil HDO process in industrial scale: (i) The chemistry of model compounds from pyrolysis bio-oils is discussed in detail including aldehydes, carboxylic acids, carbohydrates, guaiacols, furfurals, alcohols, and ketones. The reactions occur via different routes over different catalysts with different products. (ii) The reaction mechanisms of different types of catalysts are elaborated, including classical sulfided hydrotreating catalysts, noble metals, sulfides, phosphides, carbides, nitrides, non-precious metals, metal oxides, bimetallic amorphous boron-based catalysts, and reduced metal oxide bronzes. Oxygen from oxy-compounds is absorbed on coordinatively unsaturated metal sites (oxygen vacancies) on metal oxide supports through Lewis acid/base interaction, or on H in -OH that is attached to non-metal oxides such as SiO2, or even on metal sites such as noble metals. -H donation is available directly from phosphides, carbides, nitrides, Brønsted acid -OH groups or -SH groups and from metals by H spillover. The activated H species then react with oxy-organics and give hydrodeoxygenated products. (iii) The importance of supports and contribution of different supports to HDO are also covered in this review. (iv) Catalyst deactivation mechanisms were elucidated. Coking formation is proven to be the main reason for catalyst deactivation because of polymerization and polycondensation reactions. The extent of coking formation depends on the type of oxy-compounds, nature of catalysts such as acidity, and operation conditions. A robust catalyst that withstands coking, high concentration of water and poisoning, and can be regenerated easily without losing too much activity is highly desired for pyrolysis oil HDO process and finally applied in industrial scale for raw pyrolysis oil upgrading.