Mesenchymal transitions (MTs) reshape diverse tissues across both embryonic development and cancer. During development, epithelial-mesenchymal transitions (EMTs) convert 2D epithelia into highly motile 3D aggregates across tissues such as the neural crest and mesoderm. However, diverse malignancies including carcinomas, gliomas, neuroblastoma, and melanoma can co-opt these programs to promote malignant MTs and facilitate local invasion and metastasis. Using publicly available single-cell RNA-sequencing datasets, we performed pseudotime analysis to identify shared gene modules with conserved expression patterns across developmental EMTs. We then used these modules and trajectories to train MesenCoder, a conditional autoencoder model that learned a shared MT landscape across mesoderm and neural crest development. This approach uncovered a cell-state bifurcation and competing gene expression modules driving divergent MT programs during early- and later-stage mesodermal development. We subsequently screened >100 tumor datasets in the curated cancer cell atlas (Tyler et al., 2025) for shared module expression and observed that human tumors overwhelmingly employ the second MT program for later-stage mesodermal development. Because this program selectively drives MTs across vertebrate-specific mesodermal lineages, we performed an additional screen of invertebrate tumor datasets and discovered that these malignancies exclusively employed the first MT program for early mesodermal development. Together, these results demonstrate that the evolution of vertebrate-specific mesodermal lineages reconfigured tumor invasion programs across diverse human malignancies. These lineages therefore provide a better developmental paradigm for understanding heterogeneous MTs across adult and pediatric cancers.