Analysis of premalignant tissue has identified the typical order of somatic events leading to invasive tumors in several cancer types. For other cancers, premalignant tissue is unobtainable, leaving genetic progression unknown. Here, we demonstrate how to infer progression from exome sequencing of primary tumors. Our computational method, PhylogicNDT, recapitulated the previous experimentally determined genetic progression of human papillomavirus-negative (HPV) head and neck squamous cell carcinoma (HNSCC). We then evaluated HPV HNSCC, which lacks premalignant tissue, and uncovered its previously unknown progression, identifying early drivers. We converted relative timing estimates of driver mutations and HPV integration to years before diagnosis based on a clock-like mutational signature. We associated the timing of transitions to aneuploidy with increased intratumor genetic heterogeneity and shorter overall survival. Our approach can establish previously unknown early genetic progression of cancers with unobtainable premalignant tissue, supporting development of experimental models and methods for early detection, interception and prognostication.