Developing simple, cost-effective, easy-to-use, and reliable analytical devices if of utmost importance for the food industry for rapid in-line checks of their products that must comply with the provisions set by the current legislation. The purpose of this study was to develop a new electrochemical sensor for the food packaging sector. More specifically, we propose a screen-printed electrode (SPE) modified with cellulose nanocrystals (CNCs) and gold nanoparticles (AuNPs) for the quantification of 4,4'-methylene diphenyl diamine (MDA), which is one of the most important PAAs that can transfer from food packaging materials into food stuffs. The electrochemical performance of the proposed sensor (AuNPs/CNCs/SPE) in the presence of 4,4'-MDA was evaluated using cyclic voltammetry (CV). The modified AuNPs/CNCs/SPE showed the highest sensitivity for 4,4'-MDA detection, with a peak current of 9.81 μA compared with 7.08 μA for the bare SPE. The highest sensitivity for 4,4'-MDA oxidation was observed at pH = 7, whereas the detection limit was found at 57 nM and the current response of 4,4'-MDA rose linearly as its concentration increased from 0.12 μM to 100 μM. Experiments using real packaging materials revealed that employing nanoparticles dramatically improved both the sensitivity and the selectivity of the sensor, which can be thus considered as a new analytical tool for quick, simple, and accurate measurement of 4,4'-MDA during converting operations.