Natural, nonribosomal cyclotetrapeptides have traditionally been a rich source of inspiration for design of potent histone deacetylase (HDAC) inhibitors. We recently disclosed the total synthesis and full HDAC profiling of the naturally occurring azumamides ( J. Med. Chem. 2013 , 56 , 6512 ). In this work, we investigate the structural requirements for potent HDAC inhibition by macrocyclic peptides using the azumamides along with a series of unnatural analogues obtained through chemical synthesis. By solving solution NMR structures of selected macrocycles and combining these findings with molecular modeling, we pinpoint crucial enzyme-ligand interactions required for potent inhibition of HDAC3. Docking of additional natural products confirmed these features to be generally important. Combined with the structural conservation across HDACs 1-3, this suggests that while cyclotetrapeptides have provided potent and class-selective HDAC inhibitors, it will be challenging to distinguish between the three major class I deacetylases using these chemotypes.