Delineating the stock structure of highly-mobile, wide-ranging fishes subject to exploitation is a challenging task, yet one that is fundamental to optimal fisheries management. A case in point are stocks of skipjack tuna (Katsuwonus pelamis), yellowfin tuna (Thunnus albacares), bigeye tuna (Thunnus obesus) and albacore tuna (Thunnus alalunga) in the Pacific Ocean, which support important commercial, artisanal, subsistence, and recreational fisheries, and contribute roughly 70 % of global commercial tuna catches. Although some spatial and temporal structuring is recognised within these stocks, growing evidence from a range of approaches suggests that the stock structure of each tuna species is more complex than is currently assumed in both stock assessment and climate change models, and in management regimes. In a move towards improving understanding of the stock structure of skipjack, yellowfin, bigeye and South Pacific albacore tunas in the Pacific Ocean, an international workshop was held in Nouméa, New Caledonia, in October 2018 to review knowledge about their movement and stock structure in the region, define and discuss the main knowledge gaps and uncertainties concerning their stock structure, and develop biological sampling approaches to support the provision of this information. Here, we synthesise the discussions of this latter component. For each tuna species, we identify several general sampling considerations needed to reduce uncertainty, including i) the need for broadscale sampling in space, ideally covering each species’ distribution, targeting adults in spawning condition and adopting a phased approach; ii) the need for temporally-repeated sampling of the same geographical areas to assess stability in observed patterns over time; iii) the need to resolve patterns in spatial dynamics, such as those resulting from movements associated with the seasonal extensions of poleward flowing currents, from underlying stock structure, iv) the importance of adopting a multidisciplinary approach to stock identification, and v) the need for careful planning of logistics and coordination of sampling efforts across agencies. Finally, we present potential sampling designs that could be adopted to help overcome uncertainties around the initial identification of stocks and the provenance, mixing and proportional contributions of individuals in harvested assemblages, as well as how these uncertainties could be accounted for in fisheries management via the use of management strategy evaluation.