Understanding how populations adapt to changing environmental conditions is a long-standing theme in evolutionary biology. Gene expression changes have been recognized as an important driver of local adaptation, but relatively little is known regarding the direction of change and in particular, about the interplay between plastic and evolutionary gene expression. We have previously shown that the gene expression profiles of European grayling (Thymallus thymallus) populations inhabiting different thermal environments include both plastic and evolutionary components. However, whether the plastic and evolutionary responses were in the same direction was not investigated in detail, nor was the identity of the specific genes involved. In this study, we show that the plastic changes in protein expression in response to different temperatures are highly correlated with the evolutionary response in grayling subpopulations adapted to different thermal environments. This finding provides preliminary evidence that the plastic response most likely facilitates adaptation during the early phases of colonization of thermal environments. The proteins that showed significant changes in expression level between warm and cold temperature treatments were mostly related to muscle development, which is consistent with earlier findings demonstrating muscle mass differentiation between cold and warm grayling populations.