The European General Food Law, EC 178/2002 requires each stage in the supply chain to have access in its upstream and downstream trading partners. The regulation seeks to ensure that at each stage of food production, processing and movement through the supply chain steps are taken to maintain safety of the products intended for human consumption, at its highest quality. While the literature recognises the importance of food processing companies to have efficient traceability systems, there has been shortage of actual involvement of researchers in assessing the actual execution and performance of traceability systems in food processing companies, especially in developing countries. Using a qualitative approach, this study evaluates the performance of traceability systems in Tanzanian context using a case study of four fish processing companies. It explores how fish processing companies under given contextual situations (e.g. product complexity, production process complexity, supply chain complexity and organisation complexity) design and execute their traceability systems. The findings showed that despite high degree of complexity of contextual situations, all companies used paper based traceability system with minimum computer applications. Paper based traceability system is associated with several limitations, and may lead to poor performance given higher level of complexities of contextual situations.