  We investigate structures of hybrid stars, which feature quark core
surrounded by a hadronic matter mantle, with super-strong toroidal magnetic
fields in full general relativity. Modeling the equation of state (EOS) with a
first order transition by bridging the MIT bag model for the description of
quark matter and the nuclear EOS by Shen et al., we numerically construct
thousands of the equilibrium configurations to study the effects of the phase
transition. It is found that the appearance of the quark phase can affect
distributions of the magnetic fields inside the hybrid stars, making the
maximum field strength about up to 30 % larger than for the normal neutron
stars. Using the equilibrium configurations, we explore the possible
evolutionary paths to the formation of hybrid stars due to the spin-down of
magnetized rotating neutron stars. We find that the energy release by the phase
transition to the hybrid stars is quite large ($\la 10^{52} \rm erg$) even for
super strongly magnetized compact stars. Our results suggest that the strong
gravitational-wave emission and the sudden spin-up signature could be
observable signals of the QCD phase transition, possibly for a source out to
Megaparsec distances.
