Histone deacetylases (HDACs) are a family of 11 essential transcriptional regulatory enzymes. HDAC dysfunction contributes to many human disease states, including cancers and viral infections. Indeed, small molecule HDAC inhibitors are in clinical trials for treatment of cutaneous T-cell lymphomas. However, these inhibitors are relatively non-selective, and the functions and interactions of many HDACs remain poorly understood. A systematic characterization of unique and shared protein complexes among HDAC family members would provide insight into HDAC-specific functions and improved targets for therapeutic intervention. Towards these goals, we integrated fluorescence microscopy, immunoaffinity purifications, quantitative mass spectrometry, functional network analysis, and improved bioinformatics tools to build the first global protein interaction network for all eleven human HDACs in T-cells. Through optimization of label-free SAINT modeling of interaction specificity, we detected many well-known HDAC interactions as well as 200 previously unreported interactions. For instance, we identified deleted in breast cancer 1 (DBC1), a protein associated with tumor progression and known to inhibit HDAC3 and SIRT1. Our finding that DBC1 also interacts with HDAC5 and HDAC9 suggests a broader function, which we further characterized using molecular biology and biochemistry approaches. Apart from HDACs’ transcriptional roles, functional interaction profiling of novel interactions highlighted emerging roles in spliceosomal snRNP assembly and cell cycle regulation. To provide a deeper functional understanding of HDAC regulation, we designed a hybrid approach integrating label-free and isotope-labeling quantification to profile relative interaction stability across HDAC protein complexes. Interestingly, HDAC1 interactions were either highly stable within chromatin remodeling complexes or fast-exchanging associations with DNA-binding proteins and transcription factors. Collectively, our work demonstrates the effectiveness of an integrative proteomics approach in extrapolating protein functions based on interaction networks. Our global HDAC interaction dataset led to the identification of new HDAC functions and provides a rich resource for investigating HDACs in health and disease.