Large quantities of spent catalysts containing strategic metals such as molybdenum, nickel, cobalt, and vanadium, are lost after hydrodesulfurization of petroleum. Here, we review the recycling of those metals using bacteria and fungi. We analyze bioleaching approaches, utilizing both chemoautotrophic and heterotrophic microorganisms, and examine how various operational parameters influence the extraction process. The formation of soluble species in the metabolic lixiviant derived from high-sulfur feedstocks creates optimal conditions for the activity of sulfur-oxidizing microorganisms, such as Acidithiobacillus thiooxidans. In contrast, bioleaching with Penicillium simplicissimum at a pH range of 4–7 promotes the formation of stable anionic molybdate, which is advantageous for the subsequent recovery process.