Biological functions are usually performed and regulated by complexes of interacting proteins. In most cases, transcriptomic and proteomic measurements have focused on individual molecules and their functions. Despite the availability of a range of methods for the analysis of specific protein complexes, systematic analysis of the ensemble of protein complexes in a sample has remained challenging, highlighting the urgent need to identify protein complexes and their functions using high-throughput proteomic techniques. Approaches based on biochemical fractionation of intact complexes and correlation of protein profiles have shown promising performance when combining size exclusion chromatography (SEC) with highly accurate protein quantification by SWATH-MS. However, interpretation of co-fractionation datasets to protein complex composition, abundance and dynamic rearrangements remains challenging due to the limited experimentally-verified protein complexes in public knowledgebases1, because of which novel protein complexes and their changes are not identified without prior evidence. Here, we used advanced machine-learning techniques to construct a systematic framework based on Random Forest (RF) to identify novel protein complexes from SEC-SWATH-MS data and to characterize their changes across different experimental/medical conditions. With raw protein matrices of different conditions, our framework can accurately identify novel protein complexes and their changes across conditions, using hypothesis generation, data rescaling and differential analysis modules in the software package. Experiments demonstrated that the RF model achieved outstanding performance with an average AUC of 0.948, accuracy of 88.3% and MCC of 0.762 via five-fold cross-validation on three in-house/published SEC-SWATH-MS datasets (mapped to the CORUM database). Independent tests across different data acquisition methods (DDA vs. DIA) and species (human vs. mouse) also highlighted the strong generalizability of the RF model and the robustness of the prediction performance. The software is being implemented and will be freely available for prediction and analysis of novel protein complexes and their changes across conditions from co-fractionation-MS datasets.