Background People released from prison are at increased risk of death. However, no country has established a system for routine monitoring of mortality in this population. The aims of this study were to (a) evaluate a system for routine monitoring of deaths after release from prison in Australia and (b) estimate the number of deaths annually within 28 and 365 days of prison release from 2000 to 2013. Methods Persons released from prison and deaths were identified in records held by Centrelink, Australia's national provider of unemployment benefits. Estimates generated in this manner were compared with those from a study that probabilistically linked correctional records with the National Death Index (NDI), for each calendar year 2000 to 2007. Using Centrelink data, national estimates of mortality within 28 and 365 days of release were produced for each calendar year 2000 to 2013. Findings Compared with estimates based on linkage with the NDI, the estimated crude mortality rate based on Centrelink records was on average 52% lower for deaths within 28 days of release and 24% lower for deaths within 365 days of release. Nationally, over the period 2000 to 2013, we identified an average of 32 deaths per year within 28 days of release and 188 deaths per year within 365 days of release. The crude mortality rate for deaths within both 28 and 365 days of release increased over this time. Conclusions Using routinely collected unemployment benefits data we detected the majority of deaths in people recently released from prison in Australia. These data may be sufficient for routine monitoring purposes and it may be possible to adopt a similar approach in other countries. Routine surveillance of mortality in ex-prisoners serves to highlight their extreme vulnerability and provides a basis for evaluating policy reforms designed to reduce preventable deaths.