Robust stock assessments and catch limits according to CCAMLR decision rules remain to be determined for Divisions 58.4.1 and 58.4.2, and precautionary management arrangements are in place as set out in Conservation Measures 41-11 and 41-05. A research plan (WG-FSA-15/47 Rev. 1) was developed under Conservation Measure 41–01 for an Australian vessel, FV Antarctic Discovery, to participate in exploratory fishing within these Divisions. This paper reports on the fishing operation, catch composition, tagging and biological sampling undertaken by Australia in SSRUs 58.4.1E and 58.4.1G. A total of 82 research lines were completed over 27 fishing days between 29th January and 4th March 2016. Vessel logbooks recorded a total of 51980.9 kg of Antarctic toothfish (Dissostichus mawsoni) and 581.6 kg of Patagonian toothfish (Dissostichus eleginoides). Macroscopic evaluation of maturity stage indicated that both immature and mature (gonad stage ≥ 3) D. mawsoni were present in both SSRUs. The most commonly caught bycatch group was grenadiers (Macrourus spp.), followed by icefish (Channichthyidae), moray cods (Muraenolepis spp.), skates (Rajiformes) and violet cod (Antimora rostrata). Target and bycatch species were sampled for total length, standard length, whole weight, sex and gonad stage in accordance with Conservation Measure 41-01. A total of 247 D. mawsoni and 16 D. eleginoides were tagged, and 3 D. mawsoni were recaptured. Voyage outcomes are evaluated in relation to the current stock hypothesis for the region, and their progress towards achievement of the research objectives outlined in WG-FSA-15/47 Rev. 1. This is a companion paper to Maschette et al. (2016) which reports on the collection of environmental data under Objective 2 of the research plan.