Sustainable Supply Chain Management concerns with simultaneously improving social, economic and environmental performance through supply chain management practices. Sustainable practices in supply chains include reducing waste and emissions, using renewable energy, sourcing materials from sustainable sources, and promoting fair labor practices. Once practiced, this will lead to sustainable supply chains. Rembang Regency is the area with the largest capture fisheries production and production value in Central Java, Indonesia. Currently  Rembang Regency capture fisheries face various challenges on the economic performance of its fishermen, environment issue at its both fish auction site and fishing water as well as its fishermen social performance, therefore it is important to improve its capture fisheries supply chain management to achieve their supply chain sustainability. In depth interview was carried out with some fishermen and stakeholders in order to identify the root cause of their sustainable supply chain. The analysis result indicates that capture fisheries stakeholders have to make some changes in order to achieve the triple bottom line of their sustainable supply chain. Economic Performance should be improved from the auction payment lead time procedures. Whilst the environment performance should be improved through the improvements to the handling of the catch before it is brought to the auction site. Furthermore, waste management at capture waters locations needs to be a concern of the local fisheries service policy.  Social performance improvement should be done by improving its local auction procedure policies. Active participation from the stakeholders is one of the major improvement success factor.