Colloidal suspensions transform between fluid and disordered solid states as parameters such as the colloid volume fraction and the strength and nature of the colloidal interactions are varied. Seemingly subtle changes in the characteristics of the colloids can markedly alter the mechanical rigidity and flow behavior of these soft composite materials. This sensitivity creates both a scientific challenge and an opportunity for designing suspensions for specific applications. In this paper, we report a novel mechanism of gel formation in mixtures of weakly attractive nanocolloids with modest size ratio. Employing a combination of x-ray photon correlation spectroscopy, rheometry, and molecular dynamics simulations, we find that gels are stable at remarkably weaker attraction in mixtures with size ratio near two than in the corresponding monodisperse suspensions. In contrast with depletion-driven gelation at larger size ratio, gel formation in the mixtures is triggered by microphase demixing of the species into dense regions of immobile smaller colloids surrounded by clusters of mobile larger colloids that is not predicted by mean-field thermodynamic considerations. These results point to a new route for tailoring nanostructured colloidal solids through judicious combination of interparticle interaction and size distribution.