How cells in the embryo coordinate epithelial plasticity with cell fate decision in a fast changing cellular environment is largely unknown. In chick embryos, skeletal muscle formation is initiated by migrating Delta1-expressing neural crest cells that trigger NOTCH signaling and myogenesis in selected epithelial somite progenitor cells, which rapidly translocate into the nascent muscle to differentiate. Here, we uncovered at the heart of this response a signaling module encompassing NOTCH, GSK-3βSNAI1 and beta-catenin. Independent of its transcriptional function, NOTCH profoundly inhibits GSK-3β activity. As a result SNAI1 is stabilized, triggering an epithelial to mesenchymal transition. This allows the recruitment of β-catenin from the membrane, which acts as a transcriptional co-factor to activate myogenesis, independently of WNT ligand. Our results intimately associate the initiation of myogenesis to a change in cell adhesion and may reveal a general principle for coupling cell fate changes to EMT in many developmental and pathological processes.