As the most common cause of cancer death, metastasis is a complex process that involves the spread of cancer cells from the original site to other parts of the body. Diagnosis of metastasis is usually confirmed by clinical examinations and imaging, but such diagnosis is made after metastasis occurs. Early detection of metastasis plays an important role in treatment planning, which in turn has an impact on the survival of patients. So far a few methods have been developed to predict lymph node metastasis, but few methods are available for predicting distant metastasis. Motivated by a recently known gene regulation mechanism involving miRNAs, we developed a new method for predicting both lymph node metastasis and distant metastasis. We identified differential correlations of miRNAs and their target RNAs in cancer, and built prediction models using the differential correlations. Testing the method on several types of cancer showed that differential correlations of miRNAs and their target RNAs are much more powerful than expressions of known metastasis predictive genes in predicting distant metastasis as well as lymph node metastasis. Although preliminary, the method developed in this study will be useful in predicting metastasis and thereby in determining treatment options for cancer patients.