A new sustainability assessment for fishing effects (SAFE) method was used to assess the biological sustainability of 456 teleost bycatch species in Australia’s Northern Prawn Fishery. This method can quantify the effects of fishing on sustainability for large numbers of species with limited data. The fishing mortality rate of each species based on its spatial distribution (estimated from detection/non-detection data) and the catch rate based on fishery-dependent or fishery-independent data were estimated. The sustainability of each species was assessed by two biological reference points approximated from life-history parameters. The point estimates indicated that only two species (but 21 when uncertainty was included) had estimated fishing mortality rates greater than a fishing mortality rate corresponding to the maximum sustainable yield. These two species also had their upper 95% confidence intervals (but not their point estimates) greater than their minimum unsustainable fishing mortality rates. The fact that large numbers of species are sustainable can be attributed mainly to their wide distributions in unfished areas, low catch rates within fished areas and short life spans (high biological productivity). The present study demonstrates how SAFE may be a cost-effective quantitative assessment method to support ecosystem-based fishery management.