This paper aims to explore food safety traceability in the onboard food and beverage operations on cruise ships through a case study approach. Semi-structured interviews were conducted with galley and foodservice staff. Additionally, a self-administered questionnaire was designed and distributed to logistics managers and employees of three Egyptian cruise companies. Results indicated that cruise ships in this study use paper-based and manually-entered (electronically stored) data traceability systems. Managing food safety by effective product recall, complying with legislation, and improving product quality are among the most important perceived benefits identified by foodservice staff. Maintaining a good reputation, ensuring food safety, reducing foodborne illnesses, suppliers' commitment to quality specifications, and maintaining guest confidence are considered the most important benefits from implementing a food traceability system. The results also depicted that the challenges managers face implementing or improving a food traceability system included high cost, absence of unified traceability standards between cruise companies and food suppliers, shortage of skilled staff, and lack of knowledge and satisfaction with current foodservice operation systems onboard cruise ships. Other findings elucidated that the critical success factors for implementing traceability included strict food traceability legislation, ensuring the adequacy and correctness of traceability information, adopting a food traceability system by the cruise company management, the standardization of food traceability information identification, and technology support for food traceability systems implementation from government. Other factors were reported of less importance. This research concluded the urgent need for more cooperation between cruise companies, food suppliers, and relevant governmental authorities to adopt food traceability systems and the need of authorizing and setting compulsory standards and regulations.