Histone deacetylases (HDACs) are a diverse family of essential transcriptional regulatory enzymes, that function through the spatial and temporal recruitment of protein complexes. As the composition and regulation of HDAC complexes are only partially characterized, we built the first global protein interaction network for all 11 human HDACs in T cells. Integrating fluorescence microscopy, immunoaffinity purifications, quantitative mass spectrometry, and bioinformatics, we identified over 200 unreported interactions for both well-characterized and lesser-studied HDACs, a subset of which were validated by orthogonal approaches. We establish HDAC11 as a member of the survival of motor neuron complex and pinpoint a functional role in mRNA splicing. We designed a complementary label-free and metabolic-labeling mass spectrometry-based proteomics strategy for profiling interaction stability among different HDAC classes, revealing that HDAC1 interactions within chromatin-remodeling complexes are largely stable, while transcription factors preferentially exist in rapid equilibrium. Overall, this study represents a valuable resource for investigating HDAC functions in health and disease, encompassing emerging themes of HDAC regulation in cell cycle and RNA processing and a deeper functional understanding of HDAC complex stability.