An ever-increasing human population is putting major pressure on global fisheries. The need for sustainable, environmentally friendly, and safe to consume seafood from wild fishery and aquaculture practices, has never been more important. As of 2020, Australia produced ∼0.3 million tons ($3.15 Billion AUD) of seafood annually, and employs ∼17,000 people. Both production and employment levels are expected to increase, highlighting how vital the industry is. Establishing provenance of seafood is important to consumers, wild fisheries, governing bodies, and aquaculture industries. With seafood products being some of the most traded food commodities globally, there are huge concerns over food safety, traceability, mislabelling, and manipulation of products. Accurately establishing seafood provenance and validating supply chain can be difficult and sometimes impossible, thus there is an evident need for fast, cost effective and reliable solutions. We have identified key areas that must be considered when using methods to identify provenance (i.e., Species identification, geographical origins, and production methods). Additionally, we have investigated what these methods should provide (i.e., Rapid detection, reliability, and inexpensive) to become valuable to the industry and consumer. Finally, we have compared methods, examined the advantages and disadvantages, and explored new techniques, for determining the provenance of seafood.