Deciphering the cellular history of different cancers is critical for understanding tumor development and improving diagnostic and therapeutic strategies in oncology. Previous studies have shown that chromatin accessibility of the normal cell of transformation (COT) is a major determinant of a cancer\'s mutational landscape. We leveraged single-cell chromatin accessibility data from 559 healthy cell subsets to predict the COT across 36 cancer subtypes, providing unprecedented scale and resolution into the cellular beginnings of cancers. Our machine learning model predicts the COT with high robustness and accuracy, confirming both the known anatomical and cellular origins of numerous cancers, often at cell subset resolution. Unexpectedly, our work challenges traditional views that small cell lung cancer arises from neuroendocrine cells, opening new avenues for research. Our study also highlights different cellular trajectories for histological subtypes and a metaplastic state during tumorigenesis for multiple gastrointestinal cancers, which have important implications for cancer prevention, early detection, and treatment stratification.