Aim: One of the fundamental tools in biogeography is the classification of the Earth surface into spatially coherent units based on assemblage distinctiveness. However, spatial coherence of biogeographical regions may be scale-dependent, that is, it may change with changing the size of spatial units used. We ask (1) how the clusters resulting from the classification of animal assemblages at different spatial scales differ in their spatial coherence, (2) whether there are geographical trends in the patterns of spatial coherence, and (3) what factors drive these patterns at different scales and in different areas of Europe. Location: Europe. Methods: We used data from distribution atlases at two spatial scales (50 × 50 km and c. 10 × 10 km) and, for each scale, we selected four different areas across Europe, each of them covered by 250 grid cells. We classified each area based on the distributions of mammals (coarser scale only) and birds (both scales). Subsequently, we calculated the spatial coherence of resulting clusters and correlated it with environmental factors and geographical distance. Results: Coarse-scale classifications provided more spatially coherent clusters than the classifications at the finer scale and this pattern was closely related to different strength of distance decay of similarity in the species composition at different scales. Spatial coherence revealed latitudinal trends, so that coarse-scale clusters were more spatially coherent in northern Europe. Geographical distance was the best predictor of spatial patterns at the coarser scale, although this effect was strong only in central and northern Europe. At the finer scale, topography and land cover composition were the most important. Main conclusions: Spatial coherence of biogeographical regionalizations depends on scale and varies geographically. It is closely related to different beta diversity patterns at different scales and in different areas. Heterogeneous areas with high beta diversity and endemism reveal more complex patterns than areas characterized by lower beta diversity but a stronger relationship between beta diversity and distance, and consequently coherent clusters. If the development of the species distribution databases provides fine-resolution data covering large areas in the future, the issue of the scale of biogeographical regionalizations will probably become even more crucial.