Background: HIV pre-exposure prophylaxis (PrEP) is highly effective in men who have sex with men (MSM) at the individual level, but data on population-level impact are lacking. We examined whether rapid, targeted, and high-coverage roll-out of PrEP in an MSM epidemic would reduce HIV incidence in the cohort prescribed PrEP and state-wide in Australia's most populous state, New South Wales. Methods: The Expanded PrEP Implementation in Communities–New South Wales (EPIC-NSW) study is an implementation cohort study of daily co-formulated tenofovir disoproxil fumarate and emtricitabine as HIV PrEP. We recruited high-risk gay men in a New South Wales-wide network of 21 clinics. We report protocol-specified co-primary outcomes at 12 months after recruitment of the first 3700 participants: within-cohort HIV incidence; and change in population HIV diagnoses in New South Wales between the 12-month periods before and after PrEP roll-out. The study is registered with ClinicalTrials.gov, number NCT02870790. Findings: We recruited 3700 participants in the 8 months between March 1, 2016, and Oct 31, 2016. 3676 (99%) were men, 3534 (96%) identified as gay, and 149 (4%) as bisexual. Median age was 36 years (IQR 30–45 years). Overall, 3069 (83%) participants attended a visit at 12 months or later. Over 4100 person-years, two men became infected with HIV (incidence 0·048 per 100 person-years, 95% CI 0·012–0·195). Both had been non-adherent to PrEP. HIV diagnoses in MSM in New South Wales declined from 295 in the 12 months before PrEP roll-out to 221 in the 12 months after (relative risk reduction [RRR] 25·1%, 95% CI 10·5–37·4). There was a decline both in recent HIV infections (from 149 to 102, RRR 31·5%, 95% CI 11·3 to 47·3) and in other HIV diagnoses (from 146 to 119, RRR 18·5%, 95% CI −4·5 to 36·6). Interpretation: PrEP implementation was associated with a rapid decline in HIV diagnoses in the state of New South Wales, which was greatest for recent infections. As part of a combination prevention approach, rapid, targeted, high-coverage PrEP implementation is effective to reduce new HIV infections at the population level. Funding: New South Wales Ministry of Health, Gilead Sciences.