The diagnosis and treatment of soft tissue sarcomas (STSs) has been particularly difficult, because STSs are a group of highly heterogeneous tumors in terms of histopathology, histological grade, and primary site. Recent advances in genome technologies have provided an excellent opportunity to determine the complete biological characteristics of neoplastic tissues, resulting in improved diagnosis, treatment selection, and investigation of therapeutic targets. We had previously developed a novel bioinformatics method for marker gene selection and applied this method to gene expression data from STS patients. This previous analysis revealed that the extracted gene combination of macrophage migration inhibitory factor (MIF) and stearoyl-CoA desaturase 1 (SCD1) is an effective diagnostic marker to discriminate between subtypes of STSs with highly different outcomes. In the present study, we hypothesize that the combination of MIF and SCD1 is also a prognostic marker for the overall outcome of STSs. To prove this hypothesis, we first analyzed microarray data from 88 STS patients and their outcomes. Our results show that the survival rates for MIF- and SCD1-positive groups were lower than those for negative groups, and the p values of the log-rank test are 0.0146 and 0.00606, respectively. In addition, survival rates are more significantly different (p = 0.000116) between groups that are double-positive and double-negative for MIF and SCD1. Furthermore, in vitro cell growth inhibition experiments by MIF and SCD1 inhibitors support the hypothesis. These results suggest that the gene set is useful as a prognostic marker associated with tumor progression.