This paper investigates spatial correlation in the matching process of vacant jobs and job seekers. The importance of the interactions of regional labor markets in West Germany is highlighted in several dimensions. We test for spatial autocorrelation in regional hires, unemployment and vacancy levels, we examine the patterns of new matches in regions, identify clusters of regions of particularly intense interregional matching, and examine the effects of German re-unification. After setting-out a simple model of endogenous regional mobility and endogenous on-the-job search, we analyze the composition of new hires with respect to regional origin and previous employment status, the determinants of this composition, and the interaction of these characteristics. The results shed new light on the puzzle raised in the literature, which finds a large variation in unemployment rates, combined with little inter-regional migration. We find evidence in favour of labor market determined migration and against the ’internal migration puzzle’ found for other European countries and partly for the United States.