The study of phenological patterns and their dynamics provides insights into the impacts of climate change on terrestrial ecosystems. Here we present a novel analytical workflow, based on co-clustering, that enables the concurrent study of spatio-temporal patterns in spring phenology. The workflow is illustrated with a long-term time series of first leaf dates (FLD) over Europe, northern Africa, and Turkey calculated using the extended spring index models and the European E-OBS daily maximum and minimum temperatures (1950 to 2011 with a spatial resolution of 0.25°). This FLD dataset was co-clustered using the Bregman block average co-clustering with I-divergence (BBAC_I), and the results were refined using k-means. These refined co-clusters were mapped to provide a first spatially-continuous delineation of phenoregions in Europe. Our results show that the study area exhibits four main spatial phenological patterns of spring onset. The temporal dynamics of these phenological patterns indicate that the first years of the study period tend to have late spring onsets and the recent years have early spring onsets. Our results also show that the study period exhibits 12 main temporal phenological patterns of spring onset. The spatial distributions of these temporal phenological patterns show that western Turkey tends to have the most variable spring onsets. Changes in the boundaries of other phenoregions can also be observed. These results indicate that this co-clustering based analytical workflow effectively enables the simultaneous study of both spatial patterns and their temporal dynamics and of temporal patterns and their spatial dynamics in spring phenology.