This article describes the challenges of regulating and monitoring traceability and certification systems, and of ensuring the safety and authenticity of foodstuffs imported into Europe, particularly focusing on palm oils. Several measures have been implemented within palm oil supply chains to ensure that traceability can be monitored. However, these supply chains can be highly complex and, more often than not, full traceability is not achievable for stakeholders who only have access to existing systems. In Europe, measures for authenticity of palm oils are not presently as robust as those for other vegetable oils, which means that sometimes unsafe and inauthentic palm oils, often already incorporated into other products, can make their way onto supermarket shelves for unsuspecting consumers. Such instances are usually rare and are normally detected before products are purchased by consumers. Nevertheless, it is still the case that the addition of illegal and potentially harmful additives to palm oils destined for export to Europe is a regular occurrence, alerts for which can be found on the Rapid Alert System for Food and Feed (RASFF) portal. As the European Union has committed to only accept authenticated "sustainably sourced" palm oils, it is even more important to ensure that such imported oils are really from the declared source, preferably via proven analytical methods. This makes it more important that accurate and robust techniques are developed and implemented for verifying the provenance and authenticity of palm oils and their downstream products. Here, we review the underlying regulatory framework relating to traceability and authentication and assess some new and emerging chemically-based technologies that should contribute to improving the monitoring of palm oil and other vegetable oil supply chains in Europe and elsewhere.