Abstract Proteins primarily perform their functions through interactions with other proteins, making the accurate prediction of protein-protein interactions (PPIs) a fundamental problem. Experimental methods for determining PPIs are often slow and expensive, which has driven significant efforts to improve the performance of computational methods in this field. While many methods have been designed, recent thorough investigations proved that the existing methods learn exclusively from sequence similarities and node degrees. When such data leakage is avoided, performances were shown to become random. We introduce C3PI, a novel sequence-based deep learning framework designed for predicting PPIs. C3PI uses as input ProtT5 protein embeddings into a complex architecture that includes two novel components, a puzzler and an entangler, which significantly enhance the model’s performance. Through extensive comparisons with state-of-the-art methods across many datasets, C3PI consistently outperforms competing approaches, especially in key metrics such as AUPRC and AUROC. Most importantly, C3PI is the first PPI prediction method to achieve a significant improvement over random on the leakage-free gold standard dataset. C3PI is available as a web server at c3pi.csd.uwo.ca and source code from github.com/lucian-ilie/C3PI .