When a heavy fuel oil with a sulfur content of 1 percent by mass or lower is produced from a feedstock consisting of a heavy hydrocarbon oil derived from a heavy crude oil having an API degree of 30 or less and containing sulfur and metal components in amounts larger than those of ordinary crude oil, the conventional processes requires higher reaction temperature and was accompanied with a remarkably enhanced deactivation rate of the catalyst which results in a remarkable shortened lifetime thereof. Therefore, it is regarded as substantially impossible to treat the feedstock. However, the present invention makes it possible to produce a low sulfur heavy fuel oil with a sulfur content of 1 percent by mass or less by hydrotreating a mix oil of 100 parts by volume of a heavy hydrocarbon oil derived from a heavy crude oil with an API degree of 30 or less and 30 to 1000 parts by volume of a heavy hydrocarbon oil derived from a light crude oil with an API degree of 35 or greater, without lowering the degree of demetallization while retarding the deactivation rate of the catalyst.