Although many diseases are associated with cancer, the full spectrum of temporal disease correlations across cancer types has not yet been characterized. A population-wide study of longitudinal disease trajectories is needed to interrogate the general medical histories of cancer patients. Here we performed a retrospective study covering a 20-year period, using 6.9 million patients from the Danish National Patient Registry linked to 0.7 million cancer patients from the Danish Cancer Registry. Statistical analysis identified all significant disease associations occurring prior to cancer diagnoses. These associations were used to build frequently occurring, longitudinal disease trajectories. Across 17 cancer types, a total of 648 significant diagnoses correlated directly with a cancer, while 168 diagnosis trajectories of time-ordered steps were identified for seven cancer types. The most common diseases across cancer types involved cardiovascular, obesity, and genitourinary diseases. A comprehensive, publicly available web tool of interactive illustrations for all cancer disease associations is provided. By exploring the pre-cancer landscape using this large dataset, we identify disease associations that can be used to derive mechanistic hypotheses for future cancer research.