Around three to five percent of all cancers have unknown primary origin and identifying their tissue type is crucial for clinical purposes, especially for highly mutated cancers which can benefit from immunotherapy. A mutational signature describes a distinct pattern of mutations caused by a specific mutagenic process and is usually associated with a specific tissue type. For example, tobacco exposure causes a high number of C to A mutations which are frequent in lung cancer, while UV light induces a high amount of CC to TT mutations, which occur in melanomas. The previous observation motivates the goal for our study, which is to use mutational signatures contributions to predict the cancer and tissue type of highly mutated tumor samples. We use the Mutational Signatures v.3.3 cohort from the Catalogue of Somatic Mutations in Cancer (COSMIC) and consider only nine highly mutated cancer types resulting in a set of 1,477 samples. We remove artifactual signatures and consider frequently occurring signatures, resulting in a core set of twenty signatures which we used as features for our models. We tested regression and tree-based models to predict cancer and tissue type. Random forests produced superior results predicting cancer type with an accuracy, specificity and sensitivity of 83.4%, 97.9%, and 76.4%, and predicting tissue type with an accuracy, specificity and sensitivity of 89.5%, 98.0%, and 84.8%. Our approach is limited in cancers that share similar mutational signatures, e.g. our lowest accuracy (76.7%) occurs in defective mismatch repair cases from endometrial, stomach, and colorectal cancers.