The Common Agricultural Policy (CAP) was strongly criticized for the food safety crises of the 1990s which included Bovine Spongiform Encephalopathy (BSE), dioxin, foot and mouth disease and swine fever to name a few. Even though the first rules on food safety date from the very early days of the EU, a need was recognized to replace a number of these rules accumulated through the years, whose implementation was difficult to monitor, with a simpler and more comprehensive approach. The result was the General Food Law (REGULATION (EC) No 178/2002). A core concept introduced was traceability, namely “the ability to trace and follow food, feed, and ingredients through all stages of production, processing and distribution”. Furthermore after the General Agreement on Tariffs and Trade (GATT) Agreements on Agriculture (AoA) stated at the Uruguay Round and the current negotiations within the World Trade Organization (WTO), the EU has to transform a number of domestic support policies in order to be compliant with the Green Box criteria and non- or minimally trade distorting. Lastly taking into account the great concern of consumers worldwide for safe and healthy agricultural and food products, traceability would be suitable for motivating the European agricultural and food producers to differentiate their products from other competitors. The aim of this paper is to study how traceability has been included within the framework of the new CAP. In the first part of this paper we review the ways in which the issues of food safety were taken into consideration in the various reforms of the CAP from the beginning until the Agenda 2000. In the second part we briefly present the objectives and aims of the General Food Law, paying special attention to the meaning and content of traceability. Finally, in the third part we investigate the ways in which the issue of traceability has affected the shaping of the Mid-term Review of the CAP (2003) and the “Health check on CAP” (2008) through the aspects of Cross Compliance, Market Orientation and Rural Development.