Long-term vital rate and life-history data essential for sustainable harvest management are rare in tropical fisheries. Two commercially important shark species, Australian blacktip (Carcharhinus tilstoni) and spot-tail (C. sorrah) sharks in northern Australia have changed in size and population status over the last 25 years. These populations were exploited heavily from the early 1970s to the mid-1980s by foreign fishers, and since then have been harvested by a relatively small domestic fishery. We examined the differences in fork length of these species caught in 1983-1985 and 2002-2006 using Bayesian forms of generalised linear and mixed-effects models. We found clear regional differences and changes in size over time. For blacktips, sharks from the Gulf of Carpentaria have become smaller, and those from the western Northern Territory, larger over time. For spot-tail sharks, average size increased from the 1980s in the Gulf of Carpentaria, but not in the western Northern Territory. On average, sharks from the Gulf of Carpentaria were larger than those on the west coast of the Northern Territory, and females were larger than males. We suggest that changes over time and between regions in the size of spot-tail sharks are most likely due to over-exploitation in the past and subsequent recovery of populations. We discuss the uncertainty in trends for blacktip sharks in relation to fishing effort, availability of resources and species identification errors.