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. A combination of affinity capture and quantitative mass spectrometry revealed 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. HDAC inhibitors with distinct profiles have correspondingly different effects on downstream targets. We also identified the anti-inflammatory drug bufexamac as 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.