Oil palm is recognised as the most productive oil crop with highest oil yield per hectare of agriculture land. The palm oil products generated from oil palm are widely used in our daily life, contributing from food processing, personal care and hygiene sectors as well as the biofuel industry. However, the reputation of oil palm has been declining as it was accused for causing environmental and social problems, such as deforestation, workers exploitation. In order to achieve sustainable production and consumption of palm oil products, traceability of the products is very important. With the complete traceability, the origin location and quantity of palm oil products distributed along the supply chain can be identified and tracked in both the forward and backward directions. In this work, a systematic approach is developed to evaluate the traceability of palm oil products from oil palm plantations to palm oil mills. A scoring system with qualitative measure is developed to quantify the traceability of the feedstock (fresh fruit bunches). A mixed integer non-linear programming model is then developed to maximise the economic performance while tracking the traceability of the fresh fruit bunches in a supply chain. A case study in Perak, Malaysia is solved to illustrate the proposed approach. Two scenarios are solved to determine the maximum traceability and economic performance. In the first scenario, the maximum economic performance of the supply chain is determined as RM 16.8 x 106 per annum with traceability of 0.688. In scenario 2, when optimisation objective is set as maximise traceability, the maximum traceability of 0.753 with economic performance of RM 12 x 106 per annum is obtained.