Context. Period change studies offer a novel way to probe the evolution and dynamics of Cepheids. While evolutionary period changes have been well studied both observationally and theoretically, non-evolutionary period changes lack a systematic and quantitative description. Here, we deal with one such aspect of non-evolutionary period changes related to a crucial property, namely, the binarity-based nature of a Cepheid. With the advent of long-term photometry surveys covering Magellanic fields, the census of classical Cepheids in binary (or multiple) systems outside the Milky Way is timely. This may have implications for crucial aspects such as the period-luminosity relationship calibrations and our understanding of the nature of Cepheid companions. Aims. The overall objective is to have a quantitative understanding of the full picture of non-evolutionary period changes in Cepheids to develop a formalism to disentangle it from the secular evolutionary period change. In the first paper in the series, we aim to conduct a systematic search for non-evolutionary period changes to look for Cepheids in likely binary configurations and quantify their incidence rates in the Magellanic Clouds. Methods. We collected more than a decade-long time-series photometry from the publicly available, Optical Gravitational Lensing Experiment (OGLE) survey, with more than 7200 Cepheids altogether from the Large Magellanic Cloud (LMC) and Small Magellanic Cloud (SMC). Our sample contains both fundamental-mode and first-overtone mode Cepheids. Then, we calculate d the observed minus calculated (O-C) diagrams to reveal the light-travel time effect (LTTE). Finally, we calculated the minimum companion masses of the Cepheids and compared them with the predictions from Cepheid population synthesis results. Results. In our search, out of an overall sample of more than 7200 Cepheids, we found 52 candidate Cepheid binary systems in the LMC (30 fundamental and 22 first-overtone mode) and 145 in the SMC (85 fundamental and 60 first-overtone mode). The majority of the sample is characterized by orbital periods of 2000-4000 d and eccentricities of 0.2-0.5. Moreover, we report two candidates in each galaxy with the Cepheid likely existing with a giant companion. The incidence rate ratio for SMC to LMC calculated from our sample is in agreement with binary Cepheid population synthesis predictions. Conclusions. In our attempt to quantify the non-evolutionary period change connected with the LTTE, our systematic search has enriched the Cepheid binary sample by a factor of about 2 in both galaxies. The future spectroscopic follow-up can confirm the binarity nature of our sample and constrain the orbital parameters.