Deciphering the complexity of non-small cell lung cancer (NSCLC) evolutionary histories may elucidate the basis for its dismal outcome. We performed multi-region sequencing on 25 regions from seven early-stage NSCLCs. Spatial dissection revealed branched tumor evolution, with driver mutations occurring before and after subclonal diversification. Intra-tumor heterogeneity in DNA copy number alterations, translocations and endogenous APOBEC mutational processes, demonstrates that NSCLC may follow multiple distinct evolutionary trajectories simultaneously. In smokers, despite maintained carcinogen exposure, temporal dissection reveals a proportional decrease in smoking-related mutations during tumor progression, accompanied by an increase in APOBEC-related mutations. We observed genome-doubling events early in tumor development of ex-smokers, suggesting prolonged latency periods before clinical detection. Multi-region sequencing demonstrates the relentless and heterogeneous nature of genomic instability processes in early-stage NSCLCs.