I combined neutral microsatellite markers with the major histocompatibility complex (MHC) class IIB to study genetic differentiation and colonization history in Atlantic salmon, Salmo salar, in the Baltic Sea and in the north-eastern Atlantic. Baltic salmon populations have lower levels of microsatellite genetic variation, in terms of heterozygosity and allelic richness than Atlantic populations, confirming earlier findings with other genetic markers, suggesting that the Baltic Sea populations have been exposed to genetic bottlenecks, most likely at a founding event. On the other hand, the level of MHC variation was similar in the Baltic and in the north-eastern Atlantic, indicating that positive balancing selection has increased the level of MHC-variation. Both microsatellite and MHC class IIB genetic variation give strong support to the hypothesis that the Baltic salmon are of a biphyletic origin, the southern population in this study is strongly differentiated from both the northern Baltic salmon populations and from the north-eastern Atlantic populations. Salmon may have colonized the northern Baltic Sea either from the south, via the so called “Närke strait” or from the north, via a proposed historical connection between the White Sea and the northern Baltic. At microsatellites, no significant isolation-by distance was found at either colonization route. At the MHC, populations were significantly isolated by distance when assuming that colonization occurred via the “Närke strait”.