With the world’s population now in excess of 7 billion, it is vital to ensure the chemical and microbiological safety of our food, while maintaining the sustainability of its production, distribution and trade. Using UN databases, here we show that the international agro-food trade network (IFTN), with nodes and edges representing countries and import-export fluxes, respectively, has evolved into a highly heterogeneous, complex supply-chain network. Seven countries form the core of the IFTN, with high values of betweenness centrality and each trading with over 77% of all the countries in the world. Graph theoretical analysis and a dynamic food flux model show that the IFTN provides a vehicle suitable for the fast distribution of potential contaminants but unsuitable for tracing their origin. In particular, we show that high values of node betweenness and vulnerability correlate well with recorded large food poisoning outbreaks.