The hydrogenation of muconic acid (MA) to bio-adipic acid (AdA) is one of the green chemical processes that has attracted the most interest in recent years. Indeed, MA can be readily obtained from biomass through fermentative processes. Here, we aimed to investigate the synergic effect of electronic promotion that the addition of a second metal, even in small quantities, can have on Pd-based catalyst, known for its low stability. Ni and Zn were taken into consideration and two different catalysts (1%Pd8Ni2/HHT and 1%Pd8Zn2/HHT) were synthetized by sol immobilization method and supported on high-temperature, heat-treated carbon nanofibers (HHT-CNFs) that are known to enhance the stability of palladium. The catalysts were tested in MA hydrogenation and thoroughly characterized by TEM, ICP, and XPS analysis to unveil the effect of the second metal. To solve the solubility issue and have a starting material as similar as feasible to the post-fermentation conditions of the biomass, sodium muconate salt was chosen as a substrate for the reaction. All of the synthetized bimetallic catalysts showed a higher activity than monometallic Pd and better stability during the recycling tests, pointing out that even a small amount of these two metals can increase the catalytic properties of monometallic Pd.