Heavy carbonaceous feeds, including various sulfur-containing heavy petroleum oils, are simultaneously desulfurized and subjected to hydroconversion by contacting these feedstocks with alkali metal oxides in a conversion zone maintained at elevated temperatures and in the presence of hydrogen. In this manner, the feeds are substantially desulfurized, and significant upgrading of the feedstocks is also obtained as demonstrated by decreased Conradson carbon, increased API gravity, and conversion of a substantial portion of the 1,050.degree. F+ portion of the feedstream. In addition, methods for the regeneration of the alkali metal oxides from the alkali metal sulfide salts produced in the reaction zone are disclosed.