The seafood sector faces both socioeconomic and environmental sustainability challenges, as well as pressure to demonstrate progress from governments, NGOs, retailers, and consumers. To document data elements necessary in verifying key sustainability attributes and fishery progress, the sector needs to implement traceability systems accessible to fishers and other vulnerable near-shore actors. Implementation must overcome a suite of technological, social, and economic barriers. We assessed and reviewed the efficacy of several approaches attempted in a Philippines yellowfin tuna (Thunnus albacares) fishery. The current prevailing approach is a centralized, analog method of catch recording, both broadly across the Philippines and specifically in this MSC-certified fishery, where they have implemented enumerator-facilitated catch certificate recording. The fishery has begun developing, testing, and piloting new decentralized digital models, including NFC cards, RFID tags, and an app-based smartphone catch data capture. All approaches encountered barriers to uptake, and the most recent estimates suggest up to 44% of the catch in the Philippines remains unreported. We discuss additional systemic considerations necessary to advance sustainability outcomes and their documentation through traceability systems in the seafood sector originating with small-scale fishers.