An ability to understand and predict invasions is elemental for controlling the detrimental effects of introduced organisms on native biota. In eastern North America, European brown trout generally dominates over, and eventually replaces, the native brook trout. We show here that in northern Europe the pattern of replacement between these two species is reversed: when transferred to North European streams, brook trout spread extensively and partially replaced the native brown trout. The effect of brook trout on brown trout was habitat-specific: brook trout excluded the native species only in small tributary streams where the reproduction of brown trout was severely reduced, whereas in larger streams brown trout was largely unaffected. Thus, the pattern of coexistence among the two salmonids in our study area is approaching that typically observed in North American streams. In both areas, brook trout ultimately settles in small headwater streams, but the process of replacement differs profoundly: in North Europe, brook trout replaces brown trout in headwater streams, whereas in North America these same streams are the ultimate refuge area for brook trout under the invasion pressure by brown trout. Our results underline the importance of knowing species' niche characteristics to explain and predict biological invasions.