Context. Classical Cepheids are not only excellent standard candles, but also invaluable tools to test stellar evolution and pulsation theories. Rates of their pulsation period change, quantified usually through O - C diagrams, can be confronted with predictions of stellar evolution theory. On the other hand, period changes on much shorter time scales (similar to 102-104 days), attributed to non-evolutionary effects are often detected and lack detailed explanation. Aims. We aim to provide a systematic and quantitative description of irregular or non-linear period changes in Cepheids. Such a study is crucial for a complete understanding of period changes in Cepheids and is key to decoupling the evolutionary aspects from the non-evolutionary ones. Methods. We analysed part of the OGLE data for classical Cepheids in the Magellanic Clouds (MCs; from both Large Magellanic Cloud, LMC, and the Small Magellanic Cloud, SMC) using the modified Hertzsprung O - C technique. A sample of 3658 stars, with the best quality data and void of additional low-amplitude periodicities (e.g. due to non-radial pulsations), that could impact the results, was selected for analysis. Based on O - C shapes, stars were classified into three categories: no period change (class 1), linear period change (class 2), and irregular change (class 3). The Eddington-Plakidis test, wavelet analysis, Stetson index, and instantaneous period method were used to characterise class 3 candidates. We also investigated the correlation between the irregular period change in Cepheids and their metallicity environment Results. In our investigation, 33.5 +/- 0.7% of analysed stars show irregular period changes. Considering the pulsation mode, irregular period changes were detected in 16.5 +/- 0.7% of the analysed fundamental mode stars and in 68.1 +/- 1.2% of the first overtone stars. The amplitude of variability in the O - C diagrams increases with the pulsation period, and at a given pulsation period, it is larger for first overtone stars. While the increase is linear for first overtone stars, for fundamental mode stars it becomes steeper as the pulsation period increases. Time scales of the observed variability range from a few hundred to a few thousand days. Conclusions. Irregular period changes are a ubiquitous property of classical Cepheids and may impact the derivation of secular, evolutionary period change rates; hence their quantitative characterisation is essential. The nature of these changes is still unknown. Our research provides observational constraints on their modelling. The markedly higher frequency of irregular period variations in first overtone Cepheids is a key observation that must be accounted for by the models.