The nature of the Verwey transition occurring at TV ≈ 125 K in magnetite (Fe3O4) has been an outstanding problem over many decades. A complex low temperature electronic order was recently discovered and associated structural fluctuations persisting above TV are widely reported, but the origin of the underlying correlations and hence of the Verwey transition remains unclear. Here we show that local structural fluctuations in magnetite emerge below the Curie transition at TC ≈ 850 K, through X-ray pair distribution function analysis. Around 80% of the low temperature correlations emerge in proportion to magnetization below TC. This confirms that fluctuations in Fe-Fe bonding arising from magnetic order are the primary electronic instability and hence the origin of the Verwey transition. Such hidden instabilities may be important to other spin-polarised conductors and orbitally degenerate materials.