We investigate the interplay of domain formation and adhesion in mixed-lipid membranes. Giant unilamellar vesicles consisting of two- and three-component lipid mixtures are studied using confocal fluorescence microscopy. Upon driving the system towards the demixing transition, phase separation is invariably found to occur first in regions where membranes adhere to one another, despite identical lipid headgroups and negligible curvature effects. We propose a simple generic mechanism based on the suppression of thermal shape fluctuations to explain these observations. Our findings suggest novel possibilities by which biomembranes can create and utilize lateral lipid heterogeneities.