AbstractCo-evolutionary adaptive mechanisms are not only ubiquitous in nature, but also beneficial for the functioning of a variety of systems. We here consider an adaptive network of oscillators with a stochastic, fitness-based, rule of connectivity and show that it self-organizes from fragmented and incoherent states to connected and synchronized ones. The synchronization and percolation are associated to abrupt transitions and they are concurrently (and significantly) enhanced as compared to the non-adaptive case. Finally we provide evidence that only partial adaptation is sufficient to determine these enhancements. Our study, therefore, indicates that inclusion of simple adaptive mechanisms can efficiently describe some emergent features of networked systems’ collective behaviors and suggests also self-organized ways to control synchronization and percolation in natural and social systems.