The development of selective histone deacetylase (HDAC) inhibitors with anti-cancer and anti-inflammatory properties remains challenging in large part owing to the difficulty of probing the interaction of small molecules with megadalton protein complexes. We employed a combination of affinity capture and quantitative mass spectrometry to reveal the selectivity with which 16 HDAC inhibitors target multiple HDAC complexes scaffolded by ELM-SANT domain subunits including a novel mitotic deacetylase complex (MiDAC). Inhibitors clustered according to their target profiles with stronger binding of aminobenzamides to the HDAC NCoR complex than to the HDAC Sin3 complex. We identified several non-HDAC targets for hydroxamate inhibitors and also determined the anti-inflammatory drug bufexamac to be a class IIb (HDAC6, HDAC10) HDAC inhibitor. Our approach enables the discovery of novel targets and inhibitors and suggests that the selectivity of HDAC inhibitors should be evaluated in the context of HDAC complexes and not purified catalytic subunits.