By combining ab initio results for the electronic structure and phonon spectrum with the group theory, we establish the origin of the Verwey transition in Fe3O4. Two primary order parameters with X3 and Delta5 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.