Nowadays, foodborne pathogens and other food contaminants are among the major contributors to human illnesses and even deaths worldwide. There is a growing need for improvements in food safety globally. However, it is a challenge to detect and identify these harmful analytes in a rapid, sensitive, portable, and user-friendly manner. Recently, researchers have paid attention to the development of paper-based electrochemical biosensors due to their features and promising potential for food safety analysis. The use of paper in electrochemical biosensors offers several advantages such as device miniaturization, low sample consumption, inexpensive mass production, capillary force-driven fluid flow, and capability to store reagents within the pores of the paper substrate. Various paper-based electrochemical biosensors have been developed to enable the detection of foodborne pathogens and other contaminants that pose health hazards to humans. In this review, we discussed several aspects of the biosensors including different device designs (e.g., 2D and 3D devices), fabrication techniques, and electrode modification approaches that are often optimized to generate measurable signals for sensitive detection of analytes. The utilization of different nanomaterials for the modification of electrode surface to improve the detection of analytes via enzyme-, antigen/antibody-, DNA-, aptamer-, and cell-based bioassays is also described. Next, we discussed the current applications of the sensors to detect food contaminants such as foodborne pathogens, pesticides, veterinary drug residues, allergens, and heavy metals. Most of the electrochemical paper analytical devices (e-PADs) reviewed are small and portable, and therefore are suitable for field applications. Lastly, e-PADs are an excellent platform for food safety analysis owing to their user-friendliness, low cost, sensitivity, and a high potential for customization to meet certain analytical needs.