Complexome profiling is an experimental approach to identify interactions by integrating native separation of protein complexes and quantitative mass spectrometry. In a typical complexome profile, thousands of proteins are detected across typically ≤100 fractions. This relatively low resolution leads to similar abundance profiles between proteins that are not necessarily interaction partners. To address this challenge, we introduce the Gaussian Interaction Profiler (GIP), a Gaussian mixture modeling-based clustering workflow that assigns protein clusters by modeling the migration profile of each cluster. Uniquely, the GIP offers a way to prioritize actual interactors over spuriously comigrating proteins. Using previously analyzed human fibroblast complexome profiles, we show good performance of the GIP compared to other state-of-the-art tools. We further demonstrate GIP utility by applying it to complexome profiles from the transmissible lifecycle stage of malaria parasites. We unveil promising novel associations for future experimental verification, including an interaction between the vaccine target Pfs47 and the hypothetical protein PF3D7_0417000. Taken together, the GIP provides methodological advances that facilitate more accurate and automated detection of protein complexes, setting the stage for more varied and nuanced analyses in the field of complexome profiling. The complexome profiling data have been deposited to the ProteomeXchange Consortium with the dataset identifier PXD050751.