By combining {it ab initio} results for the electronic structure and phonon spectrum with the group theory, we establish the origin of the Verwey transition in Fe$_3$O$_4$. Two primary order parameters with $X_3$ and $Delta_5$ symmetries are identified. They induce the phase transformation from the high-temperature cubic to the low-temperature monoclinic structure. The on-site Coulomb interaction $U$ between 3d electrons at Fe ions plays a crucial role in this transition -- it amplifies the coupling of phonons to conduction electrons and thus opens a gap at the Fermi energy. {it Published in Phys. Rev. Lett. {bf 97}, 156402 (2006).}