Histone deacetylases (HDACs) are validated targets for treatment of certain cancer types and play numerous regulatory roles in biology, ranging from epigenetics to metabolism. Small molecules are highly important as tool compounds for probing these mechanisms as well as for the development of new medicines. Therefore, detailed mechanistic information and precise characterization of the chemical probes used to investigate the effects of HDAC enzymes are vital. We interrogated Nature's arsenal of macrocyclic nonribosomal peptide HDAC inhibitors by chemical synthesis and evaluation of more than 30 natural products and analogues. This furnished surprising trends in binding affinities for the various macrocycles, which were then exploited for the design of highly potent class I and IIb HDAC inhibitors. Furthermore, thorough kinetic investigation revealed unexpected inhibitory mechanisms of important tool compounds as well as the approved drug Istodax (romidepsin). This work provides novel inhibitors with varying potencies, selectivity profiles, and mechanisms of inhibition and, importantly, affords insight into known tool compounds that will improve the interpretation of their effects in biology and medicine.