Background: Recent debate about prostate specific antigen (PSA)-based testing for prostate cancer screening among older men has rarely considered the cost associated with screening. Methods: We assembled a population-based cohort of male Medicare beneficiaries aged 66-99 years who had never been diagnosed with prostate cancer at the end of 2005 (n = 84,699) and followed them for two years to assess the cost of PSA screening and downstream procedures (biopsy, pathology, and hospitalization due to biopsy complications) at both the national and the hospital referral region (HRR) level. The relation of screening cost to stage of prostate cancer at diagnosis at the HRR level was analyzed using multivariate Poisson models. We also evaluated the initial treatment cost of Medicare fee for service beneficiaries diagnosed with prostate cancer during 2006-2007 (n = 31,653). Results: Approximately 42.8% of the 84,699 men received PSA screening tests during the two-year study period, with 2.4% undergoing biopsy. The annual expenditures by the national fee for service Medicare program were $454 million for screening and $1.79 billion for initial treatment (in 2009 US dollars). The mean annual screening cost at the regional (HRR) level ranged from $16 to $65 per beneficiary. Downstream biopsy-related procedures (biopsy, pathology, and hospitalization due to biopsy complications) accounted for 73% of the overall screening costs and varied significantly across regions. Compared with men residing in HRRs that were in the lowest quartile for screening expenditures, men living in the highest HRR quartile were significantly more likely to be diagnosed with prostate cancer of any stage [incidence rate ratio (IRR) = 1.23, 95% confidence interval (CI): 1.07-1.42] and localized cancer (IRR = 1.31, 95% CI: 1.13-1.53). Conclusions: Medicare prostate cancer screening-related expenditures are substantial, vary considerably across regions, and are positively associated with rates of cancer diagnosis.