Histone deacetylases are well-established target enzymes involved in the pathology of different diseases including cancer and neurodegenerative disorders. The approved HDAC inhibitor drugs are associated with cellular toxicities. Different phenolic compounds have been shown to possess inhibitory activities against HDACs and are, therefore, considered safer alternatives to synthetic compounds. Here, we elucidated the binding mode and calculated the binding propensity of some of the top phenolic compounds against different isoforms representing different classes of Zn2+ ion-containing HDACs using the molecular docking approach. Our data reaffirmed the activity of the studied phenolic compounds against HDACs. Binding interaction analysis suggested that these compounds can block the activity of HDACs with or without binding to the active site zinc metal ion. Furthermore, molecular dynamics (MD) simulations were carried out on the selected crystal and docking complexes of each selected HDAC isoform. Analysis of root-mean-square displacement (RMSD) showed that the phenolic compounds demonstrated a stable binding mode over 50 ns in a way that is comparable to the cocrystal ligands. Together, these findings can aid future efforts in the search for natural inhibitors of HDACs.