An effective Food Traceability System (FTS) in a Food Supply Chain (FSC) should adequately provide all necessary information to the consumer(s), meet the requirements of the relevant agencies, and improve food safety as well as consumer confidence. New information and communication technologies are rapidly advancing, especially after the emergence of the Internet of Things (IoT). Consequently, new food traceability systems have become mainly based on IoT. Many studies have been conducted on food traceability. They mainly focused on the practical implementation and theoretical concepts. Accordingly, various definitions, technologies, and principles have been proposed. The “traceability” concept has been defined in several ways and each new definition has tried to generalize its previous ones. Nevertheless, no standard definition has been reached. Furthermore, the architecture of IoT-based food traceability systems has not yet been standardized. Similarly, used technologies in this field have not been yet well classified. This article presents an analysis of the existing definitions of food traceability, and thus proposes a new one that aims to be simpler, general, and encompassing than the previous ones. We also propose, through this article, a new architecture for IoT-based food traceability systems as well as a new classification of technologies used in this context. We do not miss discussing the applications of different technologies and future trends in the field of IoT-based food traceability systems. Mainly, an FTS can make use of three types of technologies: Identification and Monitoring Technologies (IMT), Communication Technologies (CT), and Data Management Technologies (DMT). Improving a food traceability system requires the use of the best new technologies. There is a variety of promising technologies today to enhance FTS, such as fifth-generation (5G) mobile communication systems and distributed ledger technology (DLT).