Background Australian bicycle helmet laws were first introduced in Victoria in July 1990 and the remaining Australian states, Australian Capital Territory and Northern Territory by July 1992. Previous research on helmet legislation has focused on changes in helmet wearing and bicycle-related head injury. Although it is generally accepted that bicycle helmets can reduce the risk of fatality due to head injury, there has been little research assessing the impact of helmet legislation on cycling fatalities. Methods An interrupted time series approach was used to assess the impact of bicycle helmet legislation on yearly-aggregated rates of bicycle-related fatalities per population from 1971 to 2016. Results Immediately following bicycle helmet legislation, the rate of bicycle fatalities per 1 000 000 population reduced by 46% relative to the pre-legislation trend [95% confidence interval (CI): 31, 58]. For the period 1990–2016, we estimate 1332 fewer cycling fatalities (95% CI: 1201, 1463) or an average of 49.4 per year (95% CI: 44.5, 54.2). Reductions were also observed for pedestrian fatalities; however, bicycle fatalities declined by 36% relative to pedestrian fatalities (95% CI: 12, 54). Conclusions In the absence of robust evidence showing a decline in cycling exposure following helmet legislation or other confounding factors, the reduction in Australian bicycle-related fatality appears to be primarily due to increased helmet use and not other factors.