Metastasis suppressor genes inhibit one or more steps required for metastasis without affecting primary tumor formation. Due to the complexity of the metastatic process, the development of experimental approaches for identifying genes involved in metastasis prevention has been challenging. Here we describe a genome-wide RNAi screening strategy to identify candidate metastasis suppressor genes. Following expression in weakly metastatic B16-F0 mouse melanoma cells, shRNAs were selected based upon enhanced satellite colony formation in a three-dimensional cell culture system and confirmed in a mouse experimental metastasis assay. Using this approach we discovered 22 genes whose knockdown increased metastasis without affecting primary tumor growth. We focused on one of these genes, Gas1 (Growth arrest-specific 1), because we found that it was substantially down-regulated in highly metastatic B16-F10 melanoma cells, which contributed to the high metastatic potential of this mouse cell line. We further demonstrated that Gas1 has all the expected properties of a melanoma tumor suppressor including: suppression of metastasis in a spontaneous metastasis assay, promotion of apoptosis following dissemination of cells to secondary sites, and frequent down-regulation in human melanoma metastasis-derived cell lines and metastatic tumor samples. Thus, we developed a genome-wide shRNA screening strategy that enables the discovery of new metastasis suppressor genes.