Background: Most patients with prostate cancer are diagnosed with low-grade, localized disease and may not require definitive treatment. In 2012, the U.S. Preventive Services Task Force (USPSTF) recommended against prostate cancer screening to address overdetection and overtreatment. This study sought to determine the effect of guideline changes on prostate-specific antigen (PSA) screening and initial diagnostic stage for prostate cancer. Patients and Methods: A difference-in-differences analysis was conducted to compare changes in PSA screening (exposure) relative to cholesterol testing (control) after the 2012 USPSTF guideline changes, and chi-square test was used to determine whether there was a subsequent decrease in early-stage, low-risk prostate cancer diagnoses. Data were derived from a tertiary academic medical center’s electronic health records, a national commercial insurance database (OptumLabs), and the SEER database for men aged ≥35 years before (2008–2011) and after (2013–2016) the guideline changes. Results: In both the academic center and insurance databases, PSA testing significantly decreased for all men compared with the control. The greatest decrease was among men aged 55 to 74 years at the academic center and among those aged ≥75 years in the commercial database. The proportion of early-stage prostate cancer diagnoses (<T2) decreased across age groups at the academic center and in the SEER database. Conclusions: In primary care, PSA testing decreased significantly and fewer prostate cancers were diagnosed at an early stage, suggesting provider adherence to the 2012 USPSTF guideline changes. Long-term follow-up is needed to understand the effect of decreased screening on prostate cancer survival.