Cancer of unknown primary (CUP) is a type of cancer that cannot be traced back to its original site and accounts for 3-5% of all cancers. It does not have established targeted therapies, leading to poor outcomes. We developed OncoNPC, a machine learning classifier trained on targeted next-generation sequencing data from 34,567 tumors from three institutions. OncoNPC achieved a weighted F1 score of 0.94 for high confidence predictions on known cancer types (65% of held-out samples). When applied to 971 CUP tumors from patients treated at the Dana-Farber Cancer Institute, OncoNPC identified actionable molecular alterations in 23% of the tumors. Furthermore, OncoNPC identified CUP subtypes with significantly higher polygenic germline risk for the predicted cancer type and significantly different survival outcomes, supporting its validity. Importantly, CUP patients who received first palliative intent treatments concordant with their OncoNPC-predicted cancer sites had significantly better outcomes (H.R. 0.348, 95% C.I. 0.210 - 0.570, p-value 2.32 × 10-5). OncoNPC thus provides evidence of distinct CUP subtypes and offers the potential for clinical decision support for managing patients with CUP.