Background: Patients treated with antithrombotic drugs are at risk of bleeding. Bleeding may be the first manifestation of underlying cancer. Methods: We examined new cancers diagnosed in relation to gastrointestinal or genitourinary bleeding among patients enrolled in the COMPASS trial (Cardiovascular Outcomes for People Using Anticoagulation Strategies) and determined the hazard of new cancer diagnosis after bleeding at these sites. Results: Of 27 395 patients enrolled (mean age, 68 years; women, 21%), 2678 (9.8%) experienced any (major or minor) bleeding, 713 (2.6%) experienced major bleeding, and 1084 (4.0%) were diagnosed with cancer during a mean follow-up of 23 months. Among 2678 who experienced bleeding, 257 (9.9%) were subsequently diagnosed with cancer. Gastrointestinal bleeding was associated with a 20-fold higher hazard of new gastrointestinal cancer diagnosis (7.4% versus 0.5%; hazard ratio [HR], 20.6 [95% CI, 15.2–27.8]) and 1.7-fold higher hazard of new nongastrointestinal cancer diagnosis (3.8% versus 3.1%; HR, 1.70 [95% CI, 1.20–2.40]). Genitourinary bleeding was associated with a 32-fold higher hazard of new genitourinary cancer diagnosis (15.8% versus 0.8%; HR, 32.5 [95% CI, 24.7–42.9]), and urinary bleeding was associated with a 98-fold higher hazard of new urinary cancer diagnosis (14.2% versus 0.2%; HR, 98.5; 95% CI, 68.0–142.7). Nongastrointestinal, nongenitourinary bleeding was associated with a 3-fold higher hazard of nongastrointestinal, nongenitourinary cancers (4.4% versus 1.9%; HR, 3.02 [95% CI, 2.32–3.91]). Conclusions: In patients with atherosclerosis treated with antithrombotic drugs, any gastrointestinal or genitourinary bleeding was associated with higher rates of new cancer diagnosis. Any gastrointestinal or genitourinary bleeding should prompt investigation for cancers at these sites. Clinical Trial Registration: URL: https://www.clinicaltrials.gov . Unique identifier: NCT01776424.