Rapid evolution of non-native species can facilitate invasion success, but recent reviews indicate that such microevolution rarely yields expansion of the climatic niche in the introduced habitats. However, because some invasions originate from a geographically restricted portion of the native species range and its climatic niche, it is possible that the frequency, direction and magnitude of phenotypic evolution during invasion has been underestimated. We explored the utility of niche-shift analyses in the red seaweed Gracilaria vermiculophylla, which expanded from the northeastern coastline of Japan to North America, Europe and northwestern Africa within the last 100 years. A genetically-informed climatic niche shift analysis indicates that native source populations occur in colder and highly seasonal habitats, while most non-native populations typically occur in warmer, less seasonal habitats. This climatic niche expansion predicts that non-native populations evolved greater tolerance for elevated heat conditions relative to native source populations. We assayed 935 field-collected and 325 common-garden thalli from 40 locations and as predicted, non-native populations had greater tolerance for ecologically-relevant extreme heat (40ºC) than did Japanese source populations. Non-native populations also had greater tolerance for cold and low-salinity stresses relative to source populations. The importance of local adaptation to warm temperatures during invasion was reinforced by evolution of parallel clines: populations from warmer, lower-latitude estuaries had greater heat tolerance than did populations from colder, higher-latitude estuaries in both Japan and eastern North America. We conclude that rapid evolution plays an important role in facilitating the invasion success of this and perhaps other non-native marine species. Genetically-informed ecological niche analyses readily generate clear predictions of phenotypic shifts during invasions, and may help to resolve debate over the frequency of niche conservatism versus rapid adaptation during invasion.