Species introductions provide opportunities to quantify rates and patterns of evolutionary change in response to novel environments. Alewives (Alosa pseudoharengus) are native to the East Coast of North America where they ascend coastal rivers to spawn in lakes and then return to the ocean. Some populations have become landlocked within the last 350 years and diverged phenotypically from their ancestral marine population. More recently, alewives were introduced to the Laurentian Great Lakes (~150 years ago), but these populations have not been compared to East Coast anadromous and landlocked populations. We quantified 95 years of evolution in foraging traits and overall body shape of Great Lakes alewives and compared patterns of phenotypic evolution of Great Lakes alewives to East Coast anadromous and landlocked populations. Our results suggest that gill raker spacing in Great Lakes alewives has evolved in a dynamic pattern that is consistent with responses to strong but intermittent eco‐evolutionary feedbacks with zooplankton size. Following their initial colonization of Lakes Ontario and Michigan, dense alewife populations likely depleted large‐bodied zooplankton, which drove a decrease in alewife gill raker spacing. However, the introduction of large, non‐native zooplankton to the Great Lakes in later decades resulted in an increase in gill raker spacing, and present‐day Great Lakes alewives have gill raker spacing patterns that are similar to the ancestral East Coast anadromous population. Conversely, contemporary Great Lakes alewife populations possess a gape width consistent with East Coast landlocked populations. Body shape showed remarkable parallel evolution with East Coast landlocked populations, likely due to a shared response to the loss of long‐distance movement or migrations. Our results suggest the colonization of a new environment and cessation of migration can result in rapid parallel evolution in some traits, but contingency also plays a role, and a dynamic ecosystem can also yield novel trait combinations.