Exploratory fishing for toothfish (Dissostichus spp.) in East Antarctica (Divisions 58.4.1 and 58.4.2) began in 2003. Robust stock assessment and catch limits according to CCAMLR decision rules remain to be determined for these Divisions. Accordingly, a research plan has been developed under Conservation Measure 41–01 to support a proposal for an Australian vessel to participate in exploratory fishing within Divisions 58.4.1 (SSRUs C, E, G) and 58.4.2 (SSRU E). Standardised longline fishing, in conjunction with fish biological measurements, tagging and aging, will be used to develop a stock assessment for these divisions and inform the necessary considerations of spatial structure, biomass and connectivity of toothfish populations. In addition, environmental data from CTD (conductivity, temperature and depth) and video loggers will contribute to models of toothfish habitat use. These models will inform spatial management approaches for toothfish, and the conservation of representative areas of benthic biodiversity. Additional outcomes include mapping of the bathymetry of fishable areas, and improved understanding of the distribution, relative abundance, and life histories of bycatch species.