Since 2005, the implementation of a traceability system is mandatory to all European food chain operators. The balance of costs to build and maintain the traceability system and benefits of traceability depends on the firm's traceability objectives and its resources, as reflected in characteristics, such as adopted quality management systems (QMS) or firm size. Mora and Menozzi (2005) mention that the cost of traceability is lower when firms already have a QMS in place. Moreover, US producers exporting to multiple destinations, in particular EU and Japan, need to comply with more stringent traceability regulations (De Souza Monteiro and Caswell 2004). This may request the adoption of more sophisticated and costly traceability systems. Food operators tend to have a good understanding of traceability cost, while performance benefits are usually more difficult to grasp (Verdenius 2006). This research aims at improving the understanding of how expected and actual costs and perceived benefits are influenced by firm characteristics (Meuwissen et al. 2003). This paper proposes a conceptual decision model that incorporates firm characteristics and both expected and actual costs and benefits of traceability. It is hypothesized that firm characteristics influence both expected and actual costs and benefits, while the level of traceability is influenced by expected and actual costs and perceived benefits as well as firms' characteristics. Costs can be divided into implementation and operation/maintenance costs. Benefits can arise from compliance with regulatory requirements, enhanced recall performance, improved marketing performance and increased supply chain efficiency (Sparling and Sterling 2004). The analysis uses a sample of 60 Italian fish processing businesses that were surveyed in 2008. Indicators of firm's characteristics such as number of QMS certifications, operations complexity, firm size and complexity of customer requirements, are entered as independent variables in regression analyses to predict expected and actual costs and perceived benefits which were measured on 90 point semantic scales and constant sum scales. The findings show that none of the firm characteristics investigated influence costs, while firm size and QMS certifications influence benefits in different ways. Somewhat surprisingly, firm size was found to be negatively correlated with expected and actual benefits; i.e. larger firms reported lower benefits both expected ex]ante and realized ex]post traceability system implementation. Finally, the number of QMS certifications is positively associated with expected benefits; i.e. expected benefits increase with the number of QMS certifications acquired by a firm, but no association with actual perceived benefits of traceability was found.