What makes a cancer highly metastatic is not known. Here, we inquire on the metastatic potential (MP) of tumor cells, which reflects their probability to emigrate from the primary tumor to new sites to form secondary cancers. We determine the transcriptomic landscapes of single-cell-derived clones in hybrid EMT space and define metastatic potential gradient genes (MPGGs) that linearly track MP strength. Perturbation of selected MPGGs and linked processes reveals a dynamic cellular and molecular framework of what we define as "cell-state ensembles" underlying the emergence of high MPs. To test if MPGGs predict cancer recurrence, we build the MangroveGS machine-learning model with "gene signature ensembles": MangroveGS^MPGGs robustly predicts patient tumor recurrence and metastases, outperforms all other signatures and staging systems tested, and can be extended to multiple cancer types of epithelial nature. Our findings uncover an unsuspected shared strategy for the onset of metastases that underlies clinical outcome.