Attempts to estimate natural mortality, as a single constant M, simultaneously with other model parameters in integrated assessments via CASAL for the Heard and McDonald Islands (HIMI, Division 58.5.2) Patagonian toothfish (Dissostichus eleginoides) fishery have been unsuccessful. An alternative strategy was adopted whereby the relatively long time series of catch-at-age and mark-recapture data from the main trawl ground at HIMI were used to estimate M. Catch and releases by age class for this fishery were obtained using proportions-at-length and fishery- and year-specific age–length keys (ALKs) for years 1998 to 2008. A large proportion of the recaptures of fish released in this fishery were aged and these were used to obtain recapture numbers by age class. Two alternative estimation models were programmed in R, based on alternative ordinary differential equations (ODE) for within-year population dynamics. These are the BODE model (Baranov ODE) and the CCODE model (constant catch ODE). The CCODE model is a new model for describing total mortality which disaggregates fishing and natural mortality differently to the Baranov equations and does not require a catch equation but removes catch-at-age numbers directly from the estimates of population numbers-at-age. The properties of these two models for estimation of M have been studied using simulation. In application to the data obtained for the HIMI main trawl fishery, the CCODE model gave a well-behaved profile for the log-likelihood with the corresponding estimate of M of 0.155, however, the 95% confidence bounds of the estimate were very wide ranging from 0.055 to 0.250 (based on a Poisson over-dispersion estimate of 3). In contrast, the BODE model gave unrealistic estimates of M and the annual fishing mortality rates.