The global crisis caused by the COVID-19 pandemic, in conjunction with the economic consequences and the collapse of health systems, has raised serious concerns in Europe, which is the most affected continent by the pandemic since it recorded 2,388,694 cases and 190,091 deaths (39.6% of the worldwide total), of which 71.7% (136,238) are in the United Kingdom (43,414), Italy (34,708), France (29,778), and Spain (28,338). Unlike other countries, Greece, with about 310 confirmed cases and 18 deaths per million, is one bright exception in the study and analysis of this phenomenon. Focusing on the peculiarities of the disease spreading in Greece, both in epidemiological and in implementation terms, this paper applies an exploratory analysis of COVID-19 temporal spread in Greece and proposes a methodological approach for the modelling and prediction of the disease based on the Regression Splines algorithm and the change rate of the total infections. Also, it proposes a hybrid spline regression and complex network model of social distance measures evaluating and interpreting the spread of the disease. The overall approach contributes to decision making and support of the public health system and to the fight against the pandemic.