Abstract: Recent colonization of extreme environments provides unique opportunities to study the early steps of adaptation and the potential for rapid convergent evolution. However, phenotypic shifts during recent colonization may also be due to plasticity in response to changes in the rearing environment. Here, we analyzed a suite of morphological and behavioral traits in paired surface, subterranean, and facultatively subterranean Mexican tetras (Astyanax mexicanus) from recent introductions in two separate watersheds outside of their native range. We found a variety of phenotypic and behavioral shifts between subterranean and surface populations that are similar to those observed in relatively ancient populations in Mexico. Despite this rapid morphological divergence, we found that most of these trait differences were due to plasticity in response to rearing environments. While most trait assays in common-garden, lab-raised fish indicated that phenotypic shifts in wild fish were the result of plasticity, we also found evidence of genetic control in several traits present in subterranean populations. Interestingly, wall-following behavior, an important subterranean foraging behavior, was greater in lab-born subterranean fish than in lab-born surface fish, suggesting rapid divergence of this trait between subterranean and surface populations. Thus, this study sheds light on the early steps of subterranean evolution, identifies potential rapid behavioral evolution, and suggests that plasticity in traits involving exploratory behavior may facilitate subterranean colonization.