Block copolymers, surfactants, and biomolecules form lamellar, hexagonal, and gyroid mesophases. Across these systems, the nucleation of lamellar from the disordered liquid is the easiest and the nucleation of gyroid the most challenging. This poses the question of what are the factors that determine the rates of nucleation of the mesophases and whether they are controlled by the complexity of the structures or the thermodynamics of nucleation. Here, we use molecular simulations to investigate the nucleation and thermodynamics of lamellar, hexagonal, and gyroid in a binary mixture of particles that produces the same mesophases as those of surfactants and block copolymers. We demonstrate that a combination of averaged bond-order parameters (q(2))over-bar and (q(8))over-bar identifies and distinguishes the three mesophases. We use these parameters to track the microscopic process of nucleation of each mesophase and investigate the existence of heterogeneous nucleation (cross-nucleation) between mesophases. We estimate the surface tensions of the liquid/mesophase interfaces from nucleation rates using classical nucleation theory and find that they are comparable for the three mesophases with values that are about a third of those expected for liquid-crystal interfaces. The driving forces for nucleation, on the other hand, are quite different and increase in the order gyroid < hexagonal < lamellar at any temperature. We find that the nucleation rates of the mesophases follow the order of their driving forces. We conclude that the difficulty to nucleate the gyroid originates in its lower temperature of melting and extremely low entropy of melting compared to those of the hexagonal and lamellar mesophases.